尾递归，还是递推？

关于斐波那契数的计算，写成递归式就是

func fib(n) 
{
	if(n==0||n==1) return 1;
	return fib(n-1)+fib(n-2);
}
1
2
3
4
5

改成尾递归格式变为：

func fib(n, propose, next)
{
	if(n==0) return propose;
	return fib(n-1, next, propose+next);
}

1
2
3
4
5
6

参数变复杂了。因为尾递归不允许两个子式，也不引用返回值。

print fib(10, 1, 1);
89
1
2

这里每一步n-1，最后n==0返回一个东西，看起来很地道的递归。但是不忙下结论。如果再增加一个每一步递增的参数z，改成

func fib(n, z, propose, next)
{
	if(n==0) return propose;
	return fib(n-1, z+1, next, propose+next);
}

1
2
3
4
5
6

z是个冗余的参数，对结果没有影响：

print fib(10, 0, 1, 1);
89
1
2

现在n不递减，变化一下递归结束条件，

func fib(n, z, propose, next)
{
	if(z==n) return propose;
	return fib(n, z+1, next, propose+next);
}

1
2
3
4
5
6

这是个等价变化，对结果完全没有影响。再加上打印语句观察中间步骤，

func fib(n, z, propose, next)
{
	if(z==n) return propose;
	print z+1,"\b:", next, propose+next;
	return fib(n, z+1, next, propose+next);
}

1
2
3
4
5
6
7

就成这样子了：

print fib(10, 0, 1, 1);
1: 1 2
2: 2 3
3: 3 5
4: 5 8
5: 8 13
6: 13 21
7: 21 34
8: 34 55
9: 55 89
10: 89 144
89

1
2
3
4
5
6
7
8
9
10
11
12
13

这是个递增过程。现在怎么看都像递推，递归只是做做样子的了？

同样，对于比较复杂的组合数计算，也可以写成这种尾递归格式，实际上还是应该算作递推。不过要用到传数组了，在C语言中，要显式的传入数组参数，这里采用隐式共享的output[]数组：

func cbn(n, k, z)
{
	if(z==n) return output[k];
	for(i=z>k?k:z; i>0; i--) {
		output[i]+= output[i-1];
	}
	z++;
	if(z<=k) output[z]=1;

	for(i=0; i<=z&& i<=k; i++) print output[i], "\b"; print"";
	return cbn(n, k, z);
}

1
2
3
4
5
6
7
8
9
10
11
12
13

随便选几个组合数计算一下，观察结果：

print cbn(6,3, -1);
1
1 1
1 2 1
1 3 3 1
1 4 6 4
1 5 10 10
1 6 15 20
20
print cbn(10, 5, -1);
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6
1 7 21 35 35 21
1 8 28 56 70 56
1 9 36 84 126 126
1 10 45 120 210 252
252
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

n不递减，z递增。虽然写成了递归格式，个人觉得这样写还是应该算递推吧！