揭秘-栈和递归的关系

我与数据结构有个约会，带你领略不一样的数据结构！

/*
栈最常见的应用就是递归，那么递归的实现机理是什么？他的优缺点有事什么？
我们以斐波那契数列为例：

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda 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*）
*/

#include <stdio.h>
#include <stdlib.h>

//先用循环实现,打印前30位
void f(){
    int i;
    int a[30]={0};
    a[0] = 0;
    a[1] = 1;
    printf("%d\n",a[0]);
    printf("%d\n",a[1]);
    for(i=2;i<30;i++){
        a[i] = a[i-1] +a[i-2];
        printf("%d\n",a[i]);
    }
    
    
}

//递归实现
int Fbi(int i){
    if(i<2)
        return i == 0? 0:1;
    return Fbi(i-1) + Fbi(i-2);//调用自己

}

int main(){
    //f();
    int i;
    for(i=0;i<30;i++){
        printf("%d\n",Fbi(i));
    }
    system("pause");

    return 0;
}

/*
递归调用相关问题：
1、每一个递归都可以用循环（迭代）实现，递归通常代码简洁，而循环显得冗长
2、递归并不常用，因为：大量的递归调用需要建立函数副本，会消耗大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。
因此，在递归次数很多的情况下，并不建议采用递归（有可能会死机）
*/