Tail Recursion
时间：2011-04-15 来源：glshader
Tail Recursion, 尾调用
第一次听说这个词是在<<Programming in Lua>>这本书中, 当时以为只有脚本语言这种神奇的东西才有这样功能.
最近我回顾了一下<<算法导论>>, 发现书中提到可以用Tail Recursion来优化快速排序算法. 我用Microsoft的编译器做了一下测试, 发现果然很好用.
下面是不使用Tail Recursion的程序:
int Recursion(int x)
{
if (x < 0)
return x;
else
return x + Recursion(x - 1);
}
如果x的值很大, 那么call stack会很深.
下面是采用Tail Recursion的程序:
int TailRecursion(int x, int m)
{
// __asm {int 3}; // release模式下的断点
if (x < 0)
{
return m + x;
}
else
{
return TailRecursion(x - 1, m + x);
}
}
在debug模式下, 两个函数的表现基本相同.
Release模式下(开启优化), 采用Tail Recursion的程序只占用调用栈的1层.
相关阅读 更多 +
