F#函数可以被认为是尾递归的吗?它使用TailCall.net操作码

Question

由于.net有TailCall操作码，这可以用来判断F#函数是否真的是尾递归的吗？

如果这是真的，有人制作了一个VS插件来识别尾部和非尾部函数吗？

Answer 1

请参阅F#团队博客上的这篇博客文章，了解F#如何编译尾部调用的摘要。

简而言之，

1. 直接递归尾部调用通常转换为循环
2. 相互递归和间接非递归尾调用通常被转换为.NET尾调用

但请参阅完整的帖子，了解所有血腥的细节。

Answer 2

是的，如果编译器发出tail调用指令，则该调用将是尾部递归的（从CLR 4开始，但仍有一些例外，它实际上不会是尾部递归）。但这并不一定意味着整个函数是尾部递归的。例如，我可以想象QuickSort函数被编译后，第一个递归调用不是尾递归调用，第二个调用是.

此外，仅仅因为某些函数不包含tail指令，并不一定意味着它不是尾部递归的。JIT编译器即使没有tail指令也可以识别尾部调用，并对其进行优化。

此外，F#编译器有时会以非递归的方式编译递归函数。这与正常的尾调用优化有些不同，并且不使用tail指令，但总体效果相似。