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

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

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

\[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下会进行尾递归优化

参考文档：

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

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