Java类和对象-递归算法

程序调用自身的编程技巧称为递归（recursion），它做为一种算法在程序设计语言中广泛应用。Java 支持递归，在 Java 编程中，递归是允许方法调用自身调用的属性。调用自身的方法称为是递归的。

递归的典型例子是数字的阶乘。数字 N 的阶乘是 1 到 N 之间所有整数的乘积。例如 3 的阶乘就是 1×2×3。下面的程序使用递归来计算数字的阶乘。
```java
public class Factorial {
    int fact(int n) {
        int result;
        if (n == 1) {
            return 1;
        }
        result = fact(n - 1) * n;
        return result;
    }
}
class Recursion {
    public static void main(String args[]) {
        Factorial f = new Factorial();
        System.out.println("3的阶乘是 " + f.fact(3));
        System.out.println("4的阶乘是 " + f.fact(4));
        System.out.println("5的阶乘是 " + f.fact(5));
    }
}
```
该程序产生的输出如下所示：
```java
3的阶乘是 6
4的阶乘是 24
5的阶乘是 120
> ```

如果你对递归的方法比较陌生，那么 fact( ) 的操作可能看起来有点糊涂。它是这样工作的，当 fact( ) 带着参数 1 被调用时，该方法返回 1，否则它返回 fact( n-1 ) 与 n 的乘积。为了对这个表达式求值，fact( ) 带着参数 n-1 被调用。重复这个过程直到 n 等于 1，且对该方法的调用开始返回。

为了更好地理解 fact( ) 方法是如何工作的，让我们通过一个短例子来说明。例如当计算 3 的阶乘时，对 fact( ) 的第一次调用引起参数 2 的第二次调用。这个调用将引起 fact 以参数 1的第三次调用，这个调用返回 1，这个值接着与 2（第二次调用时 n 的值）相乘。然后该结果（现为 2）返回到 fact( ) 的最初的调用，并将该结果与 3（n 的初始值）相乘。这时得到答案 6。可以在 fact( ) 中插入 println() 语句，显示每次调用的阶数以及中间结果。

当一个方法调用它自身的时候，堆栈就会给新的局部变量和自变量分配内存，方法代码就带着这些新的变量从头执行。递归调用并不产生方法新的拷贝。只有参数是新的。每当递归调用返回时，旧的局部变量和自变量就从堆栈中清除，运行从方法中的调用点重新开始。递归方法可以说是像“望远镜”一样，可以自由伸缩。

许多子程序的递归版本执行时会比它们的迭代版本要慢一点，因为它们增加了额外的方法调用的消耗。对一个方法太多的递归调用会引起堆栈崩溃。因为自变量和局部变量的存储都在堆栈中，每次调用都创建这些变量新的拷贝，堆栈有可能被耗尽。如果发生这种情况，Java 的运行时系统就会产生异常。但是，除非递归子程序疯狂运行，否则你大概不会担心这种情况。

递归的主要优点在于：某些类型的算法采用递归比采用迭代算法要更加清晰和简单。例如快速排序算法按照迭代方法是很难实现的。还有其他一些问题，特别是人工智能问题，就依赖于递归提供解决方案。最后，有些人认为递归要比迭代简单。

**当编写递归方法时，你必须使用 if 条件语句在递归调用不执行时来强制方法返回。如果你不这么做，一旦你调用方法，它将永远不会返回。这类错误在使用递归时是很常见的。尽量多地使用 println() 语句，使你可以了解程序的进程。如果发现错误，立即中止程序运行。**

下面是递归的又一个例子。递归方法 printArray( ) 打印数组 values 中的前 i 个元素。
```java
class RecTest {
    int values[];
    RecTest(int i) {
        values = new int[i];
    }
    void printArray(int i) {
        if (i == 0){
            return;
        } else {
            printArray(i - 1);
        }
        System.out.println("[" + (i - 1) + "] " + values[i - 1]);
    }
}
class Recursion2 {
    public static void main(String args[]) {
        RecTest ob = new RecTest(10);
        int i;
        for (i = 0; i < 10; i++) {
            ob.values[i] = i;
        }
        ob.printArray(10);
    }
}
```

该程序产生如下的输出：

```java
[0] 0
[1] 1
[2] 2
[3] 3
[4] 4
[5] 5
[6] 6
[7] 7
[8] 8
[9] 9
```

**经典例子：**
1、爬楼梯算法：已知一个楼梯有n个台阶，每次可以选择迈上一个或者两个台阶，求走完一共有多少种不同的走法？
方法如下：
```java
public class ClimbStairs {

public int climbStairs(int n) {
        int i=1;
		 if(n<=0)
			return 0;
		 if(n==1){
			 return i;
		 }
		 if(n==2){
			 i++;
			 return i;
		 }
		 else
			 return climbStairs(n-1)+climbStairs(n-2);
   }

public static void main(String []args){
		 ClimbStairs cs=new ClimbStairs();
		 int a =cs.climbStairs(4);
	 	 System.out.println(a);
	 }

}

```
**解析：**递归函数有返回值的比没有返回值的麻烦一点，因为一个函数只有一个返回值，但是递归还要求有基础情形的存在，所以还必须有if判断来终止递归。所以在每一个if或者else后边都有一个return，这样保证函数在任何一种情况下都有且仅有一个返回值。
分析一下这个算法：
A：如果有0个台阶，那么有0种走法，这个不用多说；
B：如果有1个台阶，那么有1种走法；
C：如果有2个台阶，那么有2种走法（一次走1个，走两次；一次走两个）；
以上的B和C就是基础情形。
D：接下来就是递归了，如果台阶数目多于2个，那么首先第一步就有两种选择：第一次走1个，或者第一次走两个。这样除了第一次后边的走法就有了两种情形：climbStairs(n-1)和climbStairs(n-2)。这样一直递归下去，直到出现到了基础情形（即n=1或n=2的情形），递归到这个地方（基础情形），然后开始回溯 ，这就是所说的和递归密切相关的“回溯”了。回溯，顾名思义就是从结果倒着回去，找到整个过程，进而分析这个路径或者说是实现的过程。

需要注意的是，这个算法实现思路上简单，但是复杂度并没有降低，还牵扯回溯保存堆栈问题(其实递归的设计尽量避免这种嵌套两个的递归方式（climb（n）中包含climb（n-1）和climb（n-2）），这种操作会使得堆栈开辟空间随着n的增大以指数型增长，最终程序很容易崩溃），而且在台阶数目多到一定数量的时候会越界（走法次数会超出int的范围），所以递归程序很大程度上就是思想实现设计上简单理解一些。

2、汉诺塔问题：一次只能移动一个盘子；不能把大盘子放在小盘子上；除去盘子在两个柱子之间移动的瞬间，盘子必须都在柱子上。（在这三点要求下把盘子从起始柱子A全部移动到目标柱子C上）

代码如下：
基础情形：n==1的时候终止递归，进行回溯。

```java
public class HanNuoTower {
	public void tower(int n,char s,char m,char e)//n个塔从s经过m最终全部移动到e
	{
		if(n==1)
			move(s,e);
		else
		{
			tower(n-1,s,e,m);
			move(s,e);
			tower(n-1,m,s,e);
		}
	}
	public void move(char s,char e){
		System.out.println("move "+s+" to "+e);
	}
	public static void main(String []args){
		HanNuoTower hnt =new HanNuoTower();
		hnt.tower(4,'A','B','C');
	}

}

```

赏

版权提示: 简记倡导尊重与保护知识产权，对有明确来源的内容注明出处。如发现本站文章存在版权或其它问题，烦请联系我，我将及时与您沟通处理。联系方式：shenco@qq.com。

技术专题

发表评论

博主已关闭全站评论! 点击跳转给我留言

目录导航 - JAVA零基础入门学习笔记