c语言-Fibonacci数列的递归实现
Fibonacci数列递归的实现
- 先来一个fibonacci数列的定义：
Fibonacci数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n – 1)+F(n – 2)（n ≥ 3，n ∈ N* 。
Fibonacci数列在程序中的实现还是很容易，他是一个典型的可以用递归现实的算法。 - 我们先来一个普通的递归写法：
int fibo(int n)
{
if(n == 1 || n == 2)
return 1;
return fibo(n-1)+fibo(n-2);
}
int main()
{
int n,result;
printf("请输入：");
scanf("%d",&n);
result = fibo(n);
printf("%d\n",result);
}
递归代码简洁，但是如果不做一定的优化，很容易出现栈溢出。以上的实现就会非常耗费内存，因为当n>2时，fibo函数需要调用自身n-2次才开始有返回值，然后开逐个返回原函数并开始计算。如果要求的n值非常大的话，可能需要同时保存成千上百个调用记录，很容易发生”栈溢出”错误（stack overflow）。
- 但是我们可以对以上实现做一个小优化-尾递归
尾递归顾名思义－在尾部递归，也就是在函数执行的最后一步调用函数自身，并且，最后一步不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。
一般来说，由于只存在一个调用记录，所以永远不会发生”栈溢出”错误。
return是用来结束执行函数、并返回结果的语句，常用来做尾递归使用。例如：上述的 return fibo(n-1)+fibo(n-2); 有＋运算符，最后一步包含了表达式；如果把＋号及后面函数调用去掉，只保留 return fibo(n-1); 则为尾递归，但这样达不到想要的结果，所以下面就需要一些小改动。
优化后的递归函数：
int fibo(int n,int i,int j)
{
if(n ==1 || n ==2)
return j;
return fibo(n-1,j,j+i);
}
int main()
{
int n,result;
printf("请输入：");
scanf("%d",&n);
result = fibo(n,1,1);
printf("%d\n",result);
}
这样一来，当fibo函数调用自身，就开始有return值，在递归结束后不用再把return值逐个返回原函数。尾递归的实现方式，编译器可以帮我们节省大量的内存消耗，妈妈再也不用我的栈溢出了！
版权声明：本文为tansss原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。