Fibonacci number | MichaelQQ.com

最近看的文章中，有兩篇[1][2]剛好都提到#Fibonacci_number ，其中一篇用了#DP 的做法，自己也試著推導一次，順便記錄下來。

Fibonacci number:

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

Fn = Fn-1 + Fn-2

一開始看到 Fibonacci number 最直覺的做法就是用#Recursive

#程式碼如下：

const fib = n => {
  if (n < 2) {
    return 1
  }
  return fib(n - 1) + fib(n - 2);
}

//or
const fib = n => n < 2 ? 1 : fib(n - 1) + fib(n - 2);

這樣的做法在數字越大就會越來越慢，因為在計算的過程中，越小的數字會被重複計算越多次

fib(6)
  |---fib(5)
  |     |---fib(4)
  |     |     |---fib(3)
  |     |     |     |---fib(2)
  |     |     |     |---fib(1)
  |     |     |---fib(2)
  |     |---fib(3)
  |           |---fib(2)
  |           |---fib(1)
  |---fib(4)
        |---fib(3)
        |     |---fib(2)
        |     |---fib(1)
        |---fib(2)

以fib(6)為例

fib(5)算1次
fib(4)算2次
fib(3)算3次 …

所以在[1]的文中，作者的方法是讓Fibonacci function有cache機制。如果直接修改Fibonacci function的話可能會像這樣：

let m = {};
const fib = n => {
  if (m[n]) {
    return m[n];
  }
  if (n < 2) {
    return 1;
  }
  m[n] = fib(n-1) + fib(n-2);
  return m[n];
}

可是我們並不想直接將cache機制加在Fibonacci function中，而是另外建立一個function，用途是將傳入的function變成有#cache 機制。但這裡作者指出另一個問題

因為Fibonacci function是recursive，所以要確保return時呼叫的>Fibonacci function也是有cache機制的Fibonacci function。

[1]的回應部分有提到一種寫起來比較簡單的做法，但這裡，我想記錄一下用Y combinator做法的推導過程。

Used in this way the Y combinator implements simple recursion. In the lambda calculus it is not possible to refer to the definition of a function in a function body. Recursion may only be achieved by passing in a function as a parameter. The Y combinator demonstrates this style of programming.

— Wikipedia Fixed-point combinator

首先，我們先將Fibonacci function做一點變形。

const afib = f => n => {
  if (n < 2) {
    return 1;
  }
  return f(n -1) + f(n - 2);
}

//or
const afib = f => n => n < 2 ? 1 : f(n - 1) + f(n - 2);

現在他已經不是一個真正Fibonacci function，但還保有其外觀。接下來我們需要個function可以讓變成真正的Fibonacci function，並且在其中加入cache機制。

const memoFib = makeMemoFib(afib);

// a function to create realFib function
const makeMemoFib = (f, m = {}) => {
  const memoFib = (n) => {
    if (m[n]) {
      return m[n]
    }
    const fib = f(memoFib);
    m[n] = fib(n);
    return m[n];
  };
  return memoFib;
};

// simplify
const makeMemoFib = (f, m = {}) => {
  const memoFib = (n) => {
    if (m[n]) {
      return m[n]
    }
    m[n] = f(memoFib)(n);
    return m[n];
  };
  return memoFib;
};

我們建立一個makeMemoFib的function，讓我們傳入被變形過的Fibonacci function，並且回傳一個有cache機制的Fibonacci function (memoFib)。

為了滿足“In the lambda calculus it is not possible to refer to the definition of a function in a function body”，我們將makeMemoFib簡化，不用另外宣告一個fib。

但是我們還是宣告了memoFib，所以我們還是需要再進一步簡化它，而可以幫助我們簡化的是：

memoFib = makeMemoFib(f, m);

const makeMemoFib = (f, m = {}) => {
  return (n) => {
    if (m[n]) {
      return m[n]
    }
    m[n] = f(makeMemoFib(f, m))(n);
    return m[n];
  };
};

這樣已經完成大半了，我們在稍作整理一下

const makeMemoFib = (f, m = {}) => (n) => {
  if (m[n]) {
    return m[n]
  }
  m[n] = f(makeMemoFib(f, m))(n);
  return m[n];
};

// simplify again
const makeMemoFib = (f, m = {}) => (n) => {
  return m[n] ? m[n] : (m[n] = f(makeMemoFib(f, m))(n));
};

// one more
const makeMemoFib = (f, m = {}) => (n) => m[n] ? m[n] : (m[n] = f(makeMemoFib(f, m))(n));

現在我們已經簡化到只剩makeMemoFib，雖然這樣還不算是一個合格的Y combinator，但對我們來說已經夠用，接下來只要把我們變形過的afib丟進去，就可以得到一個有cache機制的Fibonacci function了

const memoFib = makeMemoFib(afib);

這樣做的過程還蠻像在算#數學的，還可以試試算階層的function，也可以用類似的方法推導出來。

[2]的話則是用了ES2015的 Generator function，內容也很精彩，做法就完全不一樣了。

Reference: