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


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

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

\[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/ ),不得用于商业目的,基于本文修改后的作品务必以相同的许可发布。如有任何疑问,请 与我联系