递归
栈有一个很重要的应用:在程序设计语言中实现了递归。我们先来看一个经典的递归例子:斐波那契数列。
斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 特点:前面相邻两项之和,构成了后一项。
斐波那契数列的实现
-
一对兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。假设所有的兔子都不死亡,那么一年以后可以繁殖多少对兔子呢?
#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; }
-
假设有 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),二叉树的前中后序遍历递归实现。
递归代码简洁高效,但是也有很多弊端。比如堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等。