ITEEDU

Java Gossip: 递归方法

递归（Recursion）是在方法中呼叫自身同名方法，而呼叫者本身会先被置入内存「堆栈」（Stack）中，等到被呼叫者执行完毕之后，再从堆栈中取出之前被置入的方法继续执行。堆栈是一种「先进后出」（First In, Last Out. FILO）的数据结构，就好比您将书本置入箱中，最先放入的书会最后才取出。

Java支持方法的递归呼叫，递归的实际应用很多，举个例子来说，求最大公因子就可以使用递归来求，下面的程序是使用递归来求最大公因子的一个实例：

UseRecursion.java

import java.util.Scanner;
public class UseRecursion {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.println("输入两数:");
		System.out.print("m = ");
		int m = scanner.nextInt();
		System.out.print("n = ");
		int n = scanner.nextInt();
		System.out.println("GCD: " + gcd(m, n));
	}
	private static int gcd(int m, int n) {
		if(n == 0)
		return m;
		else
		return gcd(n, m % n);
	}
}

执行结果：

输入两数: 
m = 10 
n = 5 
GCD: 5

上面的程序是使用辗转相除法来求最大公因子；递归具有重复执行的特性，而可以使用递归求解的程序，实际上也可以使用循环来求解，例如下面的程序就是最大公因子使用循环求解的方式：

private static int gcd(int m, int n) {
	int r = 0;
	while(n != 0) {
		r = m % n;
		m = n;
		n = r;
	}
	return m;
}

那么使用递归好还是使用循环求解好？这并没有一定的答案。不过通常由于递归本身有重复执行与内存堆栈的特性，所以若在求解时需要使用到堆栈特性的数据结 构时，使用递归在设计时的逻辑会比较容易理解，程序代码设计出来也会比较简洁，然而递归会有方法呼叫的负担，因而有时会比使用循环求解时来得没有效率，不过 循环求解时若使用到堆栈时，通常在程序代码上会比较复杂。