如何应用尾部调用优化

Question

我写了一个递归函数，但是当我输入一个大数字(例如 100(时，递归需要花费很多时间。

我想在代码中应用尾部调用优化，以最大限度地减少计算时间，但我无法做到。

递归算法f(n) = f(n-1) + f(n-2)

int fib(int n)
{
if (n == 1) return n;
if (n == 0) return n;
return fib(n - 1) + fib(n - 2);
}
int _tmain(int argc, _TCHAR* argv[])
{
std::cout << "---->" << fib(3);
std::system("PAUSE");
return 0;
}

Answer 1

尾部调用优化 (TCO( 仅在函数的最后一条指令立即返回另一个函数调用(可以是递归调用(的输出时才有效。 但在这种情况下，情况并非如此。

TCO 的全部目的是允许编译器通过多个函数调用不断使用堆栈空间。 IOW，编译器可以分配单个堆栈帧(如果有的话(并一遍又一遍地重用它，而不会弄乱任何东西。

fac()函数调用自身两次，将返回值相加，然后将加法的结果返回给调用方。 因此，创建局部临时变量来接收这些返回值。 每个函数调用都必须创建一个新的堆栈帧来保存自己的局部变量，这不是恒定的堆栈使用。 而且，您的添加意味着函数的最后一条指令不是函数调用。 因此，您的代码否定了使用 TCO 的任何可能性。

Answer 2

你的代码基本上是这样做的：

int a = fac(n - 1);
int b = fac(n - 2); 
return a + b;

因此，函数返回之前的最后一个操作不是函数调用，因此此处不可能使用 TCO。