递归问题的Java实现

黄艳峰，陈伟

(1.商丘师范学院信息技术学院，河南商丘476000；2.洛阳幼儿师范学校，河南洛阳471000)

递归问题的Java实现

黄艳峰1，陈伟2

(1.商丘师范学院信息技术学院，河南商丘476000；2.洛阳幼儿师范学校，河南洛阳471000)

递归是一种常用的编程技术，借助递归算法是把一个大的问题分解成同类型的规模更小的问题的一种求解策略。介绍了递归的基本概念、递归的特点、并举例说明递归运行的流程，重点介绍了两种经典的用递归实现的算法：斐波那契数列和汉诺塔问题，并用Java语言对各个算法进行了编程实现。

递归；分解；Java；算法

1 递归的概念

递归是常用的编程技术，其基本思想是“自己调用自己”[1]，即一个使用递归的放方法是直接或间接地调用自身的方法。递归方法实际上体现了“以此类推”、“用同样的步骤重复”的思想，它可以用简单的程序解决复杂的问题。

Java递归算法是基于Java语言实现的递归算法，递归算法的实质是把问题分解成规模更小的同类问题，把一个大的问题转化为层层分解的和同类问题相似的小问题的一种求解策略。

2 递归问题的特点

递归的基本思想分成两个步骤：

一个步骤是求得范围缩小的同性质问题的结果；另一个步骤是利用这个已得到的结果和一个简单的操作求得问题的最后解答。

所有的递归方法都具有以下特点：

1)这些方法使用if-else或switch语句会导致不同的情况。

2)一个或多个基础情况用来停止递归。

3)每次递归调用都会简化原始问题，让它不断接近基础情况，直到它编程这种基础情况为止。

通常，要使用递归调用解决问题，就要将这个问题分解为子问题。每个子问题几乎与原始问题是一样的，只是规模变小了一些。可以应用相同的方法来解决递归子问题。第二个问题与原始问题一样，只是规模更小一些。这个问题的基础情况是n==0。可以使用递归来解决这个问题，如下面的代码所示：

上述代码解决了打印一条消息n次的问题。可以将这个问题分解成两个子问题：一个是打印消息一次，另一个是打印消息n-1次。

3 递归运行的流程

一个递归调用可以导致很多个递归调用，因为这个方法继续把每个子问题分解成新的子递归问题。要终止一个递归方法，必须达到问题的最后终止条件，否则会造成无限循环。当问题到达终止条件时，就将结果返回给调用者，然后调用者进行计算并将结果返回给它的上一级调用者。这个过程将会一直进行，直到结果传回给最初的调用者为止，如下图所示，显示了n=4时的递归调用情况：

图1

以求n!为例，n!可以递归地定义为：

把上述问题转化为Java代码如下：

因为对factorial的调用是调用它自己，所以这个调用是递归的。传递到factorial的参数一直递减，直到达到它的基础情况0。

4 经典递归算法示例

前面的阶乘可以很容易地不用递归进行改写，但是，在某些情况下，用其他方法不容易解决的问题可以利用递归给出一个自然、直接、简单的解法。

4.1 斐波那契数列

如下所示：

数列：0 1 1 2 3 5 8 13 21 34 55 89

下标：0 1 2 3 4 5 6 7 8 9 10 11

斐波那契数列从0和1开始，之后的每个数都是序列中前两个数的和。序列可以递归定义为：Fib(0)=0;Fib(1)=1;Fib(n)= fib(n-2)+fib(n-1);n>=2

斐波那契数列是以中世纪数学家Leonardo Fibonacci的名字命名的，他为建立兔子繁殖数量的增长模型而构造这个数列。这个数列可用于数值优化和其他许多领域。

对于给定的n，怎样求fib(n)呢？因为已知fib(0)和fib(1)，所以很容易求得fib(2)。假设已知fib(n-2)和fib(n-1)，就可以立即得到fib(n)。这样，计算fib(n)的问题就简化为计算fib(n-2)和fib (n-1)的问题。以这种方式求解，就可以递归地运用这个思路直到n递减为0或1。

所以，斐波那契数列的基础情况是n=0或n=1。若用n=0或n=1调用这个方法，就会立即返回结果。若n>=2调用这个方法，则通过递归调用把问题分解成fib(n-2)和fib(n-1)的两个子问题。计算fib(n)的递归算法可以描述为：

4.2 汉诺塔问题

汉诺塔问题是将指定个数而大小互不相同的盘子从A塔借助C塔移到B塔[2]，移动的规则如下：

1)n个盘子标记为1,2,3,...,n,而三个塔标记为A、B、C。

2)任何时候盘子都不能放在比它小的盘子的上方。

3)初始状态时，所有盘子都放在塔A上。

4)每次只能移动一个盘子，且这个盘子必须位于塔顶位置。

当盘子数量大于3时，这个问题将变得非常复杂，而因为这个问题本身就具有递归性质所以用递归解决该问题就变得很简单。

问题的基础情况是n=1。如果n=1，就可以把盘子直接从A移到B。当n>1时，可以将原始问题拆成三个子问题：

1)借助B将前n-1个盘子从A移到C

2)将盘子n从A移到B

3)借助A将n-1个盘子从C移到B

定义一个方法表示借助auxTower将n个盘子从原始塔fromTower移到目标塔toTower上：

5 结论

递归是一种很有用的程序设计技术，因为某些问题自带递归属性，所以用其他方法很难解决这些问题，使用递归就能“自然而然”地解决掉。

递归问题采用递归求解的方式具有结构清晰，可读性好，易于理解等优点[3]，使用递归看起来是一种很简单的解决方案，但因为在递归的过程中大量的使用堆栈，实际运行起来会需要大量的空间和时间，所以递归方法并不是一种高效的解决问题的方法。

[1]印旻.Java语言与面向对象程序设计[M].北京：清华大学出版社,2010.

[2]Y.Daniel Liang..Java语言程序设计基础篇[M].李娜,译.北京：机械工业出版社,2011.

[3]杨庆红,罗坚.递归问题的非递归实现方法研究与应用[J].计算机时代,2005(8)：44-45.

TP311

A

1009-3044(2017)21-0228-02

2017-04-16

黄艳峰(1977—)，女，河南兰考人，副教授，硕士，研究方向为计算机软件与理论，人工智能。