上一篇有提到會來講 Recursion 跟 DP 之間的關係，那麼這次就開門見山地說吧！
NOTE1: 跟上一篇一樣，code 使用 Javascript ES6
NOTE2: DP 是指 Dynamic Programming
NOTE3: 這篇後半頗有難度，並不適合初學者
Recursion 跟 DP 其實是同一件事情。或著更精確地說，是同一種數學解的不同程式實作。而這兩種程式時做基本上是等價的。
我們就以 Fibonacci 這個常被用來當作 DP 入門教材的題目來說吧！Fibonacci 的數學定義是
fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)所以依照這個定義來直接實作的程式會長這樣：
然後接下來教科書就會講說，可是這樣效率很慢，原因是 fib(5) = fib(4) + fib(3) ，而 fib(4) = fib(3) + fib(2)，可以看到 fib(3) 被重複呼叫了，所以說我們要用 DP 來實作。像這樣：
然後身為讀者的你可能就會說「你看吧！怎麼可能等價呢？」
其實很簡單，只要加上 cache 機制，functional 的實作也可以，像這樣：
所以理論上，只要加上 cache 的話 recursion 跟 DP 理論上就等價了。所以我就想，那 cache 這麼方便應該要把這個邏輯抽出來變成 function 才對啊！好喔！所以我就這麼做了：
可以看到這邊做了一個 memorize function，然後把 fib function 當作 input 塞進去，就得到了有 cache 版本的 fib 了！然後很方便的是，有些 library 已經幫你寫好這個 function 了！像是 lodash 裡面有提供 memoize function。
但其實這邊有個陷阱：當把 line 17 的 fib = memorize(fib) 改成 fib2 =memorize(fib) ，這樣效能就大幅下降了，為什麼呢？因為 fib function 裡面還是使用沒有 cache 版本的 fib，而不是 fib2。那怎麼辦呢？這個雷超大的啊！想要用這個方法加速，recursive function，就必須要覆蓋掉原本的 fib 變數 (line 1)，如果這個 function 是 higher order function 回傳的結果，那不就沒救了嗎？
問題的真正核心是，recursive function 會去 call 自己這個 function，廢話！不然怎麼叫做 recursive function，難道這就是 recursive 的宿命嗎？但其實這個問題並不是沒有解法的。其實解法很簡單：
讓這個 “recursive function” 從外面傳進來
於是有了這個 idea 以後，我就先把 function 變成參數了：
很明顯的，這東西根本不是 fib function，而是一個「會回傳看起來像 fib 的 function 」的 function。其中 line 3 的 f(n-1) + f(n-2) 可以看出，其實，f 才是真正的 fib function，而 genFib 就是我們產生最終 fib function 的材料。你可以會問，fib 是最後的產物，那 f 是什麼？f 其實就是還未定義的 fib function，也就是，必須要把最後的產物 fib function 在當作 genFib function 的參數塞回去。
而接下來，就要想怎麼讓上述的事情發生。像剛剛 memorize function 一樣，要先製造另外一個 function，而這個 function 會讓 genFib 轉變成為一個真正的 fib function：
fib = someFunc(genFib)有了這個 idea 以後，事情就變簡單了一點點。首先我們可以確定 someFunc 一定是回傳一個 fib，而 genFib 本身就符合這個描述，所以長這樣：
const someFunc = genFib => genFib(f)genFib 需要一個參數 f ，而這個參數本身就是 fib function，但我們先帶一個未定義的 f 進去。
再來，稍微展開 genFib(f)，變這樣
const someFunc = genFib => genFib(n => f(n))然後因為 genFib 裡面的 f 就是我們要用到 recursive function，也就是 fib。所以就把 fib = someFunc(genFib) 帶入 f
const someFunc = genFib => genFib(n => someFunc(genFib)(n))然後你讀到這邊大概會想「WTF，你到底在幹麻？」別急別急，我絕對沒有在唬爛你。下一步，把 someFunc 改名叫做 yCom，然後就完成了：
WOW Magic!!! fib 出現了！對，我絕對沒有唬爛你，不相信你可以拿去執行看看。
於是我們得到了一個 「function 自己是從外面傳進來」的 recursive function 了！也就是說，稍加修改一下 yCom function，我們就可以得到有 cache 而且沒有上面說的問題的 memorize function。
為什麼我要把這個 function 取名叫做 yCom 呢？因為，我做到一半突然想到，我曾經讀過這個東西，而這個東西叫做
Y combinator
最後感謝 Tom Chen 以及 Szu-Kai Hsu (brucehsu) 幫忙 review 本文。
UPDATE 2016/06/04: 簡化 memorize function 範例，感謝 John Lu
