C# 尾递归优化

何为尾递归

有时候我们使用递归来解决一些特定的问题，但是使用递归需要注意不要导致栈溢出，这是使用递归的一个常见问题，对于规模足够大的问题，使用递归必定会导致栈溢出。通常，我们可以通过尾递归进行优化，尾递归可以避免栈溢出的问题（暂且这样认为）。
尾递归并不是什么新奇的东西，理解起来很简单，对于递归，如果上层调用的返回结果不依赖子调用的结果，那么，这就是一个尾递归。例如：

///这是一个简单的尾递归例子
namespace tail
{
    class Program
    {
        static void Main(string[] args)
        {
            var test=RetrieveData(100000000000000);
        }

        static long RetrieveData(long unit)
        {
            if (unit == 0)
                return unit;
            return RetrieveData(--unit);
        }
    }
}

等等，好像有什么地方不对

从上面的例子分析，代码依旧会导致栈溢出，不是吗？是的，聪明的你答对了。那为什么说尾递归可以避免栈溢出问题？当然，从刚才的结论看，这个问题提的并不准确，尾递归并不能避免栈溢出问题。
仔细想想，尾递归结构和循环结构是类似的，上面的尾递归可以写成：

//糟糕的例子，但是就这样吧
static long RetriveData(long unit)
{
    for(long i=unit;i<=0;i--)
        continue;
    return 0;
}

请忽略这个蠢函数什么都不做的事实。回到问题上，循环结构并不会导致栈溢出，基于这种结构上的对应，编译器可以对尾递归进行优化，重复使用栈上的递归函数，而不是每次调用都进行压栈操作，以此来避免栈溢出的问题。所以，完善的结论是：通过编译器优化，尾递归可以避免栈溢出的问题。

那么C#呢？

不幸的是，对于微软的 C# Compiler， 只有 x64 Release 才有尾递归优化。作为对比，我们分析其与 x86 Release 下编译后的代码的区别，看看编译器是如何优化尾递归调用的。

分析两者的 IL 代码，可以发现它们并没有什么区别，所以，真正进行优化操作的是 JIT 编译器。
分析两者的汇编代码：

可以看出，在 ASM_x64 中，递归调用没有重复压栈，而是在栈内跳转，类似于循环结构，以此来避免栈溢出问题。