Willy's Fish教學筆記』

前一陣子主管心血來潮的出了一道題給我
題目是這樣的
2+3是固定的
之後+的都是前兩位的和
2+3+5(5=2+3)
2+3+5+8(8=3+5)
以此類推
求第n個的和
n=1 Ans=  2
n=3 Ans=10
n=4 Ans=18

要求寫下兩個method
一個用迴圈
一個不能用任何迴圈
以下是我的解答

public int oneToN_total_0(int n) {
    int result = 0;
    ArrayList<Integer> list = new ArrayList<>();
    list.add(2);
    list.add(3);
    for (int i = 0; i < n; i++) {
        if (i >= 2) {
            list.add(list.get(i - 2) + list.get(i - 1));
        }
        result += list.get(i);
    }
    return result;
}

public int oneToN_total_1(int n) {
    int result = 5, first = 2, second = 3, temp = 0;
    for (int i = 3; i <= n; i++) {
        result += first + second;
        temp = first;
        first = second;
        second = temp + second;
    }
    if (n == 1) return 2;
    if (n == 2) return 5;
    return result;
}

public int oneToN_total_2(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 2;
    if (n == 2) return 5;
    return oneToN_total_2(n - 1) - oneToN_total_2(n - 3) 
         + oneToN_total_2(n - 1);
}

由於主管說我用ArrayList滿偷吃步的
所以oneToN_total_1()是我寫的另一種「標準答案」
而三個method跑出來
n 0~9 的答案都是 0, 2, 5, 10, 18, 31, 52, 86, 141, 230

那不用迴圈的method又是如何寫呢？
沒錯，就是用遞迴的方式
但效率方面真的不太佳
與上面兩個method相比停頓了好久

由此可見
「遞迴只應天上有，凡人應當用迴圈」
還滿有道理的…

其實遞迴這東西是從數學定義來的
數學的定義方法裡有一種叫做遞歸定義
而遞迴的程式其實就只是把這種概念直接程式化而已
點我到wiki看遞歸定義

ptt中有大大對遞迴看法的總結如下
遞迴這東西其實就是數學歸納法
所以只要數學歸納法搞得懂就搞得懂遞迴
點我看更詳細總結
 

那遞迴倒底有什麼優缺點呢？讓我們來看看
優點：
(1)可增加程式的可讀性。
(2)可處理較複雜的問題。

缺點：
(1)需要花費較多的時間。
(2)利用暫存堆疊(Stack)的觀念，需要額外的儲存空間。

也就是說遞迴式可以增進結構化程式設計的可讀性
不過針對執行效率而言
還是以所謂的for或while迴路更能節省執行時間與資源

點我看遞迴式講義介紹

參考資料：
https://market.cloud.edu.tw/content/senior/computer/ks_ks/book/algodata/algorithm/algo43.htm
https://webptt.com/m.aspx?n=bbs/Programming/M.1382291312.A.693.html