斐波那契数列递归解法

递归解斐波那契数列

斐波那契数列最直观的递归解法：

int fib(int n){
          
   
	if (n<2) {
          
    
		return n;
	} else {
          
   
		return fib(n-1) + fib(n-2);
	}	
}

然而这种解法效率很低，会进行很多重复运算 例如：当计算 fib(5) 时，我们共需要计算1次 fib(4)，2次 fib(3)，3次 fib(2)，5次 fib(1) 和3次 fib(0)。这些无意义的重复计算使得递归效率极低。

递归解法的优化

实际上像斐波那契这样的数列还有很多，他们都满足相同的规律，即从第三项开始，每一项等于前两项之和。这样的数列被统称为可加数列（additive sequence），不同的只是他们的第一项 t0 和 t1。

斐波那契数列： 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , … 0, 1, 1, 2, 3, 5, 8,13,21, 34,55,dots 0,1,1,2,3,5,8,13,21,34,55,…

如果我们将它的第一项和第二项换成3和7，就会变成： 3 , 7 , 10 , 17 , 27 , 44 , 71 , 115 , 186 , … 3, 7, 10, 17, 27, 44, 71,115,186, dots 3,7,10,17,27,44,71,115,186,…

因此，求解斐波那契数列第n项的问题可以被转化成求解一个可加数列的第n项的问题，而且只需要知道 t0 和 t1 的值，我们就可以求出数列中的任意一项。所以我们可以写出一个函数：

int additiveSequence(int n, int t0, int t1);

下一步就是实现这个函数。继续观察可加数列，我们可以发现一个可加数列S中的第n项等于将这个数列每一项都向前移一位的新数列的第n-1项。

例如，原数列中的t6 = 71: 当我们将该数列每一位都向前移动一位，得到一个新数列，此时 t5 = 71： 而这个新的 t0 等于原数列的 t1，新的 t1 等于原数列的 t0 + t1。

因此函数可以写为：

int additiveSequence(int n, int t0, int t1){
          
   
	if (n==0) return t0;
	if (n==1) return t1;
	return additiveSequence(n-1, t1, t0+t1);
}

递归求解斐波那契数列的完整函数就可写为：

int fib(int n){
          
   
	return additiveSequence(n, 0, 1);
}

int additiveSequence(int n, int t0, int t1){
          
   
	if (n==0) return t0;
	if (n==1) return t1;
	return additiveSequence(n-1, t1, t0+t1);
}