From Gossip@caterpillar

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;
}

那麼使用遞迴好還是使用迴圈求解好？這並沒有一定的答案。不過通常由於遞迴本身有重複執行與記憶體堆疊的特性，所以若在求解時需要使用到堆疊特性的資料結構時，使用遞迴在設計時的邏輯會比較容易理解，程式碼設計出來也會比較簡潔，然而遞迴會有方法呼叫的負擔，因而有時會比使用迴圈求解時來得沒有效率，不過迴圈求解時若使用到堆疊時，通常在程式碼上會比較複雜。