原文来自《挑战程序设计竞赛》

深度优先搜索（DFS）和宽度优先搜索（BFS）都是常见的搜索算法。在学习DFS和BFS之前，我们首先得知道递归函数的概念。

通俗地讲，一个函数自己调用自己的行为就叫递归，该函数就叫递归函数。如计算一个数的阶乘，就可以利用递归来实现。 我们知道一个数的阶乘可以等于这个数乘上这个数减1的阶乘，如 3 ! = 3 × 2 ! 3!=3\times2! 3!=3×2!，便有递推式：

n ! = n × ( n − 1 ) ! n!=n\times(n-1)! n!=n×(n−1)!

规定 0 ! = 1 0!=1 0!=1，便可以很容易地编写出如下函数：

递归函数必须要有循环退出的条件，在这段代码中， n = = 0 n==0 n==0就是循环退出的条件。如果没有循环退出的条件，那么函数就会无限地调用下去，导致程序崩溃。 下面是计算阶乘的递归过程：

类似地，我们可以试着编写计算斐波那契数列的某一项的递归函数。斐波那契数列的定义如下：

设数列 { a n } , \{a_n\}, {an​},若满足 a 0 = 0 a_0=0 a0​=0, a 1 = 1 a_1=1 a1​=1, a n = a n − 1 + a n − 2 ( n ≥ 2 ) a_n=a_{n-1}+a_{n-2}(n\geq2) an​=an−1​+an−2​(n≥2),则称数列 { a n } \{a_n\} {an​}为斐波那契数列

根据定义，我们知道斐波那契数列的递推式为 a n = a n − 1 + a n − 2 a_n=a_{n-1}+a_{n-2} an​=an−1​+an−2​，循环退出的条件为 n = 0 n=0 n=0或 n = 1 n=1 n=1，这样就可以很容易地写出该递归函数：