递归

栈有一个很重要的应用：在程序设计语言中实现了递归。我们先来看一个经典的递归例子：斐波那契数列。

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 特点：前面相邻两项之和，构成了后一项。

斐波那契数列的实现

1. 一对兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。假设所有的兔子都不死亡，那么一年以后可以繁殖多少对兔子呢？

   #include <stdio.h>
   
   // 斐波那契的递归函数 
   int Fbi(int i)
   {
       if (i < 2)
           return i == 0 ? 0 : 1;
       return Fbi(i-1) + Fbi(i-2);     
   }
   
   int main()
   {
       int i;
       for (i=1; i<=12; i++)
           printf("%d\n", Fbi(i));
       return 0;
   }
   

2. 假设有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶总共有多少种走法？

   #include <stdio.h>
   
   // 递归实现方式
   int f(int n)
   {
       if (n == 1) 
           return 1;
       if (n == 2)
           return 2;
       return f(n-1) + f(n-2);
   }
   
   // 迭代循环的非递归实现方式
   int f(int n)
   {   
       if (n == 1)
           return 1;
       if (n == 2) 
           return 2;
   
       int ret = 0;
       int pre = 2;
       int prepre = 1;
       int i;      
       for (i=3; i<=n; ++i) {
           ret = pre + prepre;
           prepre = pre;
           pre = ret;
       }
       return ret;
   }
   
   int main()
   {
       printf("%d\n", f(6)); // 6 个台阶总共有 13 种走法
       return 0;
   }
   

   下面分别为问题 1 和 2 的数学函数定义：

递归是一种应用非常广泛的算法（或者编程技巧），很多数据结构和算法的编码实现都要用到递归，比如图的深度优先搜索（DFS），二叉树的前中后序遍历递归实现。

递归代码简洁高效，但是也有很多弊端。比如堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等。