递归算法想必大家都已经很熟悉了。递归算法虽然简单，但是容易导致一些性能问题，于是就有了尾递归这种优化算法。
首先我们先看看递归算法的性能问题是在哪里？
比如我们有一个常见的算法，叫做阶乘算法。
$$f(x)=1\cdot2\cdot3\cdots!x$$
他的递归实现是这样子的
$$\begin{array}{1}f(x)=x f(x-1)\\qquad,=x\cdot(x-1)f(x-2)\\qquad,\cdots\\qquad,=x\cdot(x-1)\cdot(x-2)\cdots1\end{array}$$
实现代码如下
//C#实现
int Foo(int x)
{
if(x==1)
{
return 1;
}
return x*Foo(x-1);
}#python 实现
def foo(x):
if(x==1):
return 1
return x*foo(x-1)我们看到每次调用foo方法的时候，又会执行一次foo方法。
此时程序会将当前上下文压栈，计算出下一个foo的值，然后再出栈和x进行相乘
所以对于foo(3)的调用，整个栈的情况是这样的
$$\begin{array}{1}foo(3)\3\cdot foo(2)\3\cdot 2\cdot foo(1)\3\cdot 2\cdot1\3\cdot 2\6\end{array}$$
那么尾递归呢？
它是指函数的最后一个位置（或者动作）是调用自身
我们把上面的方法改一下尾递归
//C#尾递归实现
int Foo(int x, int result=1)
{
if(x==1)
{
return result;
}
return Foo(x-1,x*result);
}#python 尾递归实现
def foo2(x,result=1):
if(x==1):
return result
return foo2(x-1,result*x)这里有两个需要注意的点
- 参数里面多了一个result，表示返回值。那么原本需要在内存中记录的信息，从方法参数中传入了
- 最后的递归调用处位于return，递归的方法只需要返回一个值，而不需要同上一层递归调用的方法再做交互
那么这么有什么好处呢？
好处就是“聪明”的编译器在准备入栈时发现，咦，这里的递归放回值不需要做任何计算，直接返回更上一层就好了。那么存储上下文没有啥好处，不存了！！
所以此时的栈使用情况就会变成
$$\begin{array}{1}foo2(3)\foo2(2,3)\foo2(1,6)\6\end{array}$$
内存占用，显著减少
不过尾递归虽好，但是还是要依赖于各种编译器的支持。
目前我知道的是python是支持的，探索c#之尾递归编译器优化 - 蘑菇先生 - 博客园文章中表示64位release下会进行尾递归优化
参考文档：