关于尾部的递归优化的斐波那契的数列。
f(n) = f(n-1) * n;
当 n = 1时，f(1) = 1;
f(5) = 5 * f(4) = 5 * 4 * f(3) = 5 * 4 * 3 * f(2) = 5 * 4 * 3 * 2 * f(1) = 120
反过来怎么走,等价于如下形式。
f'(4, 5)
f'(3, 20)
f'(2, 60)
f'(1, 120)
变成两个参数，就是一个函数。
f(n) = g(n-1, n)
g(x, y) = g(x-1, x * y)
when x = 1, g(x, y) = y.
用c语言描述就是
int f(int n) {
return g(n-1, n);
}
int g(x, y) {
if (x == 1) return y;
else
return g(x - 1, x * y);
}
其中y的位置以函数参数的形式记录了中间结果。
按原有的方式为
int f(int n) {
if (n == 1) return 1;
else return n * f(n-1);
}
在C语言的环境下，没有做递归优化的时候，这个时候堆栈是没有差别的。原因如下
f(5)
f(4)
f(3)
f(2)
f(1)
然后一级一级的return back。
g(4,5)
g(3, 20)
g(2, 60)
g(1, 120)
然后return back。这是没有做优化的时候。而优化恰好在于
g(4,5)=g(3,20)=g(2,60)=g(1,120).所以此时堆栈上不用保存中间等的返回地址，可以覆盖原有占用堆栈的部分。
应该就没有错了。
1 #include <stdio.h>
2
3 /**
4 * Description: old function.
5 */
6 int fold(int n) {
7 if (n == 1)
8 return 1;
9 else
10 return n * fold(n-1);
11 }
12
13 int g(int x, int y) {
14 if (x == 1)
15 return y;
16 else
17 return g(x - 1, x * y);
18 }
19
20 int fnew(int n) {
21 return g(n - 1, n);
22 }
23
24 int main() {
25 printf("1:%d\n", fold(5));
26 printf("2:%d\n", fnew(6));
27 return 1;
28 }
评论