递归（the repeated application of a recursive procedure or definition.--摘自维基百科）重复调用的过程。
使用递归法来构造fibonacci数列应该是十分简明易得的,如下：
int Fibonacci(int n){//假设fibonacci数列从f(0)开始；
if(n==0 || n==1){
return 1;
}else{
return Fibonacci(n-1)+Fibonacci(n-2);//递归调用 ：容易导致栈溢出
}
}
正如我在这段代码注释一样，递归调用最大的问题也就是栈深的问题。在我的笔记本上，当n>200时，需要快一分钟时间才能计算出来。所以，你看到，当递归量加大，不仅影响栈空间，而且增加时间的计算，其中不乏同一个量的持续计算；采用递归方法，fibonacci数列的时间复杂度为O(2^n),这是难以忍受的。
再看fibonacci数列，我们可以列举几个fibonacci数看一看求解过程；
F(1)=1;F(0)=1;
f(2)=f(1)+f(0)=2;
f(3)=f(1)+f(2)=f(0)+(1)+f(1);
不知道你是否看到重复计算的过程，当n=4时，采取递归时，f(1)重复计算了一次，但是f(2)在之前的计算中已经得出结果，所以如果可以采取一个数据量或者采取某种数据结构来储存fibonacci数列之前产生的数，则可以提高时间效率；这就是迭代法解决fibonacci数的核心；
如下，采取迭代法的代码：
int Fibonacci(int n) { //迭代调用
int current,pre,last;
pre=0;last=1;
if(n==0){
return 0;
}else if(n==1){
return 1;
}
else{
for(int i=2;i<=n;i++){
current=pre+last;
pre=last;
last=current;
}
return current;
}
}
所以你看到该迭代将fibonacci数列的复杂度减少到O(n)；
受此启发，我们是否可以就在递归的过程中实现类似迭代的过程，及通过减少递归的项数，增加每一层递归的中间数；尾递归就是此方面的代表：
< a subroutine call performed as the final action of a procedure>
如下是尾递归的代码：
int fiboTail(int n, int a, int b)//尾递归
{
if (n == 0) return a;
if (n == 1) return b;
return fiboTail(n - 1, b, a + b);
}
你看到如此简洁，如递归那般简洁的代码，却有着递归难以企及的复杂度优化，核心是通过a,b来构造中间数，易得它的复杂度也是O(n);
转载请注明原文地址: https://ju.6miu.com/read-1295446.html
