昨天介紹了 recursion，並寫出用 recursion 來計算階層的 function
今天得寸進尺的來做其他 recursion 的練習

Fibonacci sequence 費波那契數列/兔子數列

義大利不只有義大利麵，還有數學家（咦）
來自義大利的費波那契提出了費氏數列，其呈現如下

1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , .....
規律為『前兩項相加總和』會等於後一項的數值

1(第1項)+1(第2項)=2（第3項）
可以類推為
valueOf "N-2" Element + valueOf "N-1" Element = valueOf "N" Element

Write a function that calculate the value of Fibonacci numbers F(n), n=18
試寫出計算費氏數列的 function ，並取得第 18 項的值

Answer:

function calcFibonacci(n) {
    let result = 0;
    if (n === 2 || n === 1) {
        return result + 1;
    }
    result = calcFibonacci(n - 1) + calcFibonacci(n - 2);
    return result;
}

console.log(calcFibonacci(18)); // 2584

The big O for calcFibonacci is O(n^2)
This is the refined version.

 function calcFibonacci(n, memo = {}) {
     if (n === 1 || n === 2) {
         return 1;
     }
     if (memo[n]) {
         return memo[n];
     }
     memo[n] = calcFibonacci(n - 1, memo) + calcFibonacci(n - 2, memo);
     return memo[n];
}

完成了以上的練習
是不是對 recursion 有更深入的認識了呢？

相關資源

javascript recursion functions exercises
https://www.w3resource.com/javascript-exercises/javascript-recursion-functions-exercises.php
fibonacci calculator
https://www.calculatorsoup.com/calculators/discretemathematics/fibonacci-calculator.php
recursion
https://javascript.info/recursion