程序员必须掌握的递归算法

1 引言

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。一个方法或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

例如求和问题：若要求解S₁₀₀ = 1 + 2 + 3 + 4 + …. + 100的值，通过循环的方式代码如下：

int sum = 0; for (int i = 1; i <= 100; i++) { sum = sum + i; } 

通过递归方式是如何求解呢？由 1 + 2 + 3 + 4 + …. + 100 可以分解为 ( 1 + 2 + 3 + 4 + …. + 99) + 100，可以看出

S₁₀₀ = S₉₉ + 100，可以得出 S_n = S_n-1 + n。通过递归的方式代码如下：

public int sum(int n) { if (n == 1) { return 1; } else { return sum(n - 1) + n; } } 

通过递归代码可以看出，sum() 方法中又调用了其自身，只是将传入的参数发生改变。这种程序调用自身的方式就是递归。

2 应用场景

什么样的问题才可以使用递归的方式求解呢？构成递归需要具备两个条件：

（1）子问题与原始问题为同样的事情，二者的求解方法是相同的，且子问题比原始问题更易求解。

（2）递归不能无限制地调用本身，必须有个递归出口。递归出口对应的情形相对简单，可以化简为非递归状况处理。

3 实例

3.1 斐波那契数列

斐波那契数列（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*）。

问题分析：

斐波那契数列的对于原问题F(n)的求解可以转为对F(n-1)、F(n-2)两个子问题的求解，故符合条件（1）。由F(1)=1，F(2)=1,可以得出斐波那契数列问题是有递归出口的，递归出口对应F(1) = 1，F(2) = 1。求解斐波那契数列的代码如下：

public class FibonacciSequence { public static void main(String[] args){ System.out.println(Fribonacci(9)); } public static int Fribonacci(int n){ if(n <= 2) return 1; else return Fribonacci(n-1)+Fribonacci(n-2); } } 

3.2 阶乘问题

阶乘问题的数学表达式为：n! = n * (n-1) * (n-2) * …* 1 (n>0)。通过分析可以得出n! = (n-1)! * n。令F(n) = n!，则F(n) = F(n-1) * n。则阶乘问题符合条件（1）。由0! = 1，可以得出F(0) = 1。则阶乘问题符合条件（2），递归出口为F(0) = 1。利用递归求解阶乘问题代码如下：

int factorial(int n) { int sum = 0; if (0 == n) return 1; else sum = n * factorial(n-1); return sum; } 

3.3 树的遍历

对于树遍历问题在之前树的专题中已经详细介绍，这里不再赘述。二叉树的遍历代码如下：

/*前序遍历算法*/ void PreOderTraverse(BiTree T) { if(T == NULL) return; printf("%c",T->data); //显示结点数据，可以更改为其他对结点操作 PreOderTraverse(T->lchild); //先遍历左子树 PreOderTraverse(T->rchild); //最后遍历右子树 } /*中序遍历递归算法*/ void InOderTraverse(BiTree T) { if(T == NULL) return ; InOderTraverse(T->lchild); //中序遍历左子树 printf("%c",T->data); //显示结点数据，可以更改为其他对结点的操作 InOderTraverse(T->rchild); //最后中序遍历右子树 } /*后序遍历递归算法*/ void PostOderTraverse(T) { if(T==NULL) return; PostOderTraverse(T->lchild); //先遍历左子树 PostsOderTraverse(T->rchild); //再遍历右子树 printf("%c",T->data); //显示结点数可以更改为其他对结点数据 } 

通过代码可以看出，二叉树的遍历过程使用递归方式实现既有助于理解，又简化了代码量。

4 结语

使用递归求解问题就好比，你手中有一把钥匙想要打开一扇门。当你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。

递归算法的应用十分广泛，应用递归算法可以使你的代码根据“优雅”。