尾递归

什么叫递归，就是自身调用自身不断解决子问题的过程。比如著名的斐波那契数列：

return f(n-2)+f(n-1);

我们会看到，每次return都会在程序栈中压入两个函数，这就是尾递归和普通递归最大的区别。

比如我们计算f(5)：

f(5)
f(4)+f(3)
f(3)+f(2)+f(2)+f(1)
f(2)+f(1)+f(1)+f(0)+f(1)+f(0)+1
f(1)+f(0)+1+1+1+1+1+1
1+1+1+1+1+1+1+1
8

试想如果是100呢，那么压入栈的函数栈帧可能会超出程序空间导致出错。

而尾递归则不同。

#include<stdio.h>

int tail(int n,int first, int second, int begin)
{
	if(n == begin)
	{
		return first+second;
	}else{
		return tail(n,second, first+second, begin+1);
	}
}

int fib(int n)
{
	if(n == 0 || n == 1) return 1;
	else{
		return tail(n,1,1,2);
	}
}

int main()
{
	int n;
	scanf("%d",&n);
	printf("%d",fib(n));
	return 0;
}

它的每一次压函数栈帧都是固定大小，只需要记录tail(n,second, first+second, begin+1)即可。而部分语言对此有优化，会将函数栈帧替换。从而保证tail在运行过程中不会占据过大的空间。

fib(5)
tail(5,1,1,2)
tail(5,1,2,3)
tail(5,2,3,4)
tail(5,3,5,5)
8

另外一个有效的判断方式是每递归一次，压入栈，离问题越远；每一次弹栈，离问题越近。

而尾递归则是每一次计算都会离结果越近。

比较本质的一种说法是, 当该函数在递归调用时, 其返回值不依赖于其自身的处理, 比如说返回值带有加减法等需要额外运算的操作. 此时, 编译器会直接将调用者弹栈, 将参数传入被调用者压入栈, 所以一赠一减, 就不会膨胀到占据过大的空间.