int Fib(int n)
{
if(n < 2)
return 1;
return Fib(n-1) + Fib(n-2);
}
这段代码无法进行尾递归优化,因为在最后一次调用 Fib
返回之前无法评估 +
。 (实际上我认为这也是 Expert F# 中使用的示例,但对此不确定。)
int Fib(int n, int a, int b)
{
if(n == 0)
return a+b;
return Fib(n-1,a+b,a);
}
由于在最后一次调用Fib之前所有参数都已经被计算出来,且在调用之后没有任何操作需要执行,因此可以对此版本进行尾调用优化,以便丢弃当前的栈帧。