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)
递归函数c语言规则
{
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 overfl
ow）。
但是我们可以对以上实现做⼀个⼩优化-尾递归
尾递归顾名思义－在尾部递归，也就是在函数执⾏的最后⼀步调⽤函数⾃⾝，并且，最后⼀步不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本⾝⽆论调⽤多少次，都只占⽤⼀个栈帧，不会出现栈溢出的情况。
⼀般来说，由于只存在⼀个调⽤记录，所以永远不会发⽣"栈溢出"错误。
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值逐个返回原函数。尾递归的实现⽅式，编译器可以帮我们节省⼤量的内存消耗，妈妈再也不⽤我的栈溢出了！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。