安安的code日記

遞迴

就是指函式自己呼叫自己，但遞迴會增加程式在執行時的負擔，資料太多時記憶體甚至會不夠。 但有些問題用遞迴來解決，可以增加效益，這就要自行做判斷取捨。

為什麼遞迴執行時會效能比較不好呢？因為每次在函式中呼叫函式時，上一層的函式就進行到一半，在stack記憶體中佔據一個空間後，等待下一層的函式執行完畢回報，於是這樣層層堆積，如果遞迴的次數太多，可能就會發生溢位的狀況，所以遞迴要有停止機制(Base Case)。

費氏數列

遞迴的經典例子之一：費氏數列，(1.1.2.3.5.8.13.21......)，第0項為0，第一項為1，後一項為前兩項的和

寫成數學公式為

• 
• {\displaystyle F_{1}=1}
• {\displaystyle F_{n}=F_{n-1}+F_{n-2}}（n≧2）

用迴圈寫的話，第一種方法：陣列紀錄數列的每一項數值

優點：邏輯比較簡單好懂

缺點：因為記錄每一項，記憶體佔用空間較多

public static void main(String[] args) {
    //用迴圈寫費氏
    int fi[] = new int[5];
    for (int i = 0; i < fi.length; i++) {
        if (i == 0 || i == 1) {    
            fi[i] = 1;
            continue;
        }
        fi[i] = fi[i - 1] + fi[i - 2];
    }

    for (int i = 0; i < fi.length; i++) {
        System.out.print(fi[i] + " ");
    }

}

迴圈的第二種方法：設定變數a和b，一個存b入前兩項的和

圖解，就是一個變數a,b一直向右推移的過程，先將原ab和，放入tmp變數，a放入b向右推一格，b再放入tmp(a+b)，向右推一格.......

這邊設定 i 從3開始，是自己希望 i 等於幾 就代表b現在是數列中的第幾個數

public static void main(String[] args) {
    //用迴圈寫費氏，得出第i個數值
    int a = 1;
    int b = 1;
    int index = 10;  //求第10項的數值
    for (int i = 3; i < index + 1; i++) {
        int tmp = a + b;
        a = b;
        b = tmp;
    }
    System.out.print(b);


}

再來是用遞迴寫費氏的函式，也很單純，將數學公式帶入即可

//費氏數列第幾個
public static int fiIndex(int x) {
    if(x==1||x==0){   //base case
        return  x;
    }
    return fiIndex(x-1) + fiIndex(x-2);
}

將數列列出的函氏

//費氏數列列出
public static int[] fi(int x) {
    int[] fi = new int[x];
    for (int i = 0; i < fi.length; i++) {
        int index = i + 1;
        fi[i] = fiIndex(index);
    }
    return fi;
}

河內塔

這個題目也很經典，看老師的教學我能理解code的概念，但想不通他是怎麼透過這樣簡單的三行兩遞迴，算出這麼多步驟的。實際上運行的詳細步驟真的想了解啊.....

河內塔規則：河內塔維基百科

基礎概念步驟就是：

1.先將除了底盤以外的盤子 移到中間

2.再將最底部的盤子 移到最右邊

3.最後將中間的全部盤子 移到最右邊

重點是，當一根住子上的盤子數量不是1時，就必須重複上述的步驟

//河內塔
public static void hanoi(int x, int a, int b, int c) {    //(盤子數量，柱子代號a，柱子代號b，柱子代號c) 
    if (x == 1) {    //函式設定當盤子的數量為1的時候，移動參數a到參數c
        System.out.println(a + "->" + c);
        return;
    }
    hanoi(x - 1, a, c, b);  //當盤子數量不是1的時候，移動除底盤以外的盤子 從a到b
    System.out.println(a + "->" + c);  //再將剩餘的底盤 從a移到c
    hanoi(x - 1, b, a, c);   //把移到b的其他底盤，從b移到c
}

這邊常看到的疑問有

Q 為什麼這樣就能確保大盤子不會疊在小盤子上呢？

A 因為依據上面的步驟，只要盤子上面有疊盤子，一律是將底部以外的盤子 先移到輔助的柱子上，再去移動剩餘的盤子，一直重複呼叫自身函式，直到盤子數量為1。

看個動畫會更清楚 來源: https://www.bilibili.com/video/BV1Zh411y7XB?share_source=copy_web

自己也畫了步驟演示，再遞迴的過程中，會不斷的替換三根柱子的位子，維持a>c的動作

有一個影片也說明得很詳細，推薦：https://www.bilibili.com/video/BV1HE411W71E?share_source=copy_web