在程式碼的實作中，大方向上可分出兩大類實作：



I   迴圈 (for loop, while loop)

II  遞迴 (Recursion)



基本上，任何一種實作都能在兩者之間互換，但也通常會有一者實作起來更順手。

在此單元，我們來看到遞迴的實作示範：



遞迴觀念：老和尚說故事



不知道大家有沒有聽過下面這個故事：

「從前有座山，山上有座廟，廟裡住著老和尚與小和尚，有一天老和尚跟小和尚講故事說：從前有座山，山上有座廟，廟裡住著・・・・・」



遞迴的概念與此非常相似，會一直呼叫自己，直到遇到終止條件！



遞迴實作：費氏數列(Fibonacci)



首先，來看到一個有趣的小知識：

在生活中，其實我們眼睛很習慣看1:1.618這個俗稱「黃金比例」的形體，比如說夏天常見的颱風、宇宙銀河系的分佈都是如此





那這個黃金比例與費氏數列的關係在哪？



費氏數列長這個樣子：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233



觀察一下可以看出，除了第一個跟第二個數字之外，後面的數字都是前兩個數字的相加

ex. 1 = 0 + 1

ex. 2 = 1 + 1

ex. 8 = 3 + 5



而如果我們將一個數字 ÷ 前一個數字，我們將得到越來越接近1.618這個黃金比例：

ex. 8 ÷ 5 = 1.6

ex. 55 ÷ 34 = 1.617...

ex. 233 ÷ 144 = 1.618...



所以到這邊，我們知道電腦科學學生必學的這個費氏數列，並不是一個冷冰冰的數學公式，而是一個自然甚至是生活中常見的現象。



那現在，我們要透過程式，把費氏數列透過程式碼的形式展現出來，同時我們也來看看「遞迴(recursion)」的實作方式：

public static Integer fibonacci(int n){
    if (n == 0) return 0;   // first number
    if (n == 1) return 1;   // second number

    /** next round **/
    return fibonacci(n - 2) + fibonacci(n - 1);
}


以上這個實作，我們就透過每一輪之中，把n-1, n-2之後再呼叫方法自己本身，也就能拿到我們最後的數字。

這邊也建議大家，如果是第一次學遞迴，可以拿張紙把整個分支展開畫出來，仔細觀察一下遞迴的路線是怎麼「長」出來的。

這邊提供測試程式碼，有興趣的學員可以自己跑跑看：

public static void main(String[] args) {
    for (int i = 0; i < 20; i++) {
        System.out.print(fibonacci(i) + " ");
        // 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
    }
}