2020-1-6-什么是尾递归

递归算法想必大家都已经很熟悉了。递归算法虽然简单，但是容易导致一些性能问题，于是就有了尾递归这种优化算法。

首先我们先看看递归算法的性能问题是在哪里？

比如我们有一个常见的算法，叫做阶乘算法。

他的递归实现是这样子的

实现代码如下

//C#实现
int Foo(int x)
{
    if(x==1)
    {
        return 1;
    }
	return x*Foo(x-1);
}

#python 实现
def foo(x):
    if(x==):
        return 
    return x*foo(x-)

我们看到每次调用foo方法的时候，又会执行一次foo方法。

此时程序会将当前上下文压栈，计算出下一个foo的值，然后再出栈和x进行相乘

所以对于foo(3)的调用，整个栈的情况是这样的

那么尾递归呢？

它是指函数的最后一个位置（或者动作）是调用自身

我们把上面的方法改一下尾递归

//C#尾递归实现
int Foo(int x, int result=1)
{
    if(x==1)
    {
        return result;
    }
	return Foo(x-1,x*result);
}

#python 尾递归实现
def foo2(x,result=):
    if(x==):
        return result
    return foo2(x-,result*x)

这里有两个需要注意的点

• 参数里面多了一个result，表示返回值。那么原本需要在内存中记录的信息，从方法参数中传入了
• 最后的递归调用处位于return，递归的方法只需要返回一个值，而不需要同上一层递归调用的方法再做交互

那么这么有什么好处呢？

好处就是“聪明”的编译器在准备入栈时发现，咦，这里的递归放回值不需要做任何计算，直接返回更上一层就好了。那么存储上下文没有啥好处，不存了！！

所以此时的栈使用情况就会变成

内存占用，显著减少

不过尾递归虽好，但是还是要依赖于各种编译器的支持。

目前我知道的是python是支持的，探索c#之尾递归编译器优化 - 蘑菇先生 - 博客园文章中表示64位release下会进行尾递归优化

参考文档：

• 尾调用 - 维基百科，自由的百科全书
• 探索c#之尾递归编译器优化 - 蘑菇先生 - 博客园

本文会经常更新，请阅读原文： https://xinyuehtx.github.io/post/%E4%BB%80%E4%B9%88%E6%98%AF%E5%B0%BE%E9%80%92%E5%BD%92.html ，以避免陈旧错误知识的误导，同时有更好的阅读体验。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。欢迎转载、使用、重新发布，但务必保留文章署名黄腾霄（包含链接： https://xinyuehtx.github.io ），不得用于商业目的，基于本文修改后的作品务必以相同的许可发布。如有任何疑问，请 与我联系 。