好端端的”斐波那契“是怎麼變成這樣的,因吹斯聽,我們來回放一下。 ...
前幾天同事發了這麼一段代碼
(fn =>
(f => f(f))(f => fn(n => f(f)(n)))
)(g =>
n => [1, 2].indexOf(n) > -1 ? 1 : g(n - 1) + g(n - 2)
)(10);
猜你看這段代碼時,一定是這樣的心情:
好端端的斐波那契
是怎麼變成這樣的,因吹斯聽,我們來回放一下。
從正常的寫法開始:
const fib = n => [1, 2].indexOf(n) >= 0 ? 1 : fib(n - 1) + fib(n - 2);
為了讓上面看起來不像遞歸,改寫一下。
把遞歸調用改成調用參數g
。
const wrappedFib = g => n => [1, 2].indexOf(n) >= 0 ? 1 : g(n - 1) + g(n - 2);
不管g
傳什麼,例如就傳null
,1,2兩項我都可以計算了,因為壓根和g
無關。
wrappedFib(null)(1);
wrappedFib(null)(2);
如果要計算第3項,那我的g
就可以是wrappedFib(null)
。
let g = wrappedFib(null);
wrappedFib(g)(3);
同理,第4項
let g = wrappedFib(wrappedFib(null));
wrappedFib(g)(4);
第5項......第N項我就不列了
看起來需要構造一個g
,他由無限層的wrappedFib
組成。
遞歸的思想
const g = n => wrappedFib(g)(n);
運行一下試試吧
const wrappedFib = g => n => [1, 2].indexOf(n) >= 0 ? 1 : g(n - 1) + g(n - 2);
const g = n => wrappedFib(g)(n);
console.log(wrappedFib(g)(10));
題外話
g
本身就是由無限層wrappedFib
組成的
所以wrappedFib(g)
和g
是等價的
因此,也可以直接調console.log(g(10));
const g = n => wrappedFib(g)(n);
又看到了明顯的遞歸對不對,試著把它藏起來,思想跟開始的wrappedFib
函數一樣,通過參數傳進來,這段要花點時間理解。
const g = (f => n => wrappedFib(f(f))(n))(f => n => wrappedFib(f(f))(n));
方法本身和方法傳參是一樣的,換個寫法
const g = (f => f(f))(f => n => wrappedFib(f(f))(n));
能到這裡,我們和最終的代碼已經很接近了,把g
中的wrappedFib
去掉,通過參數fn
傳進來。
const gWaitForWrappedFib = fn => (f => f(f))(f => n => fn(f(f))(n));
const g = gWaitForWrappedFib(wrappedFib);
好了,去掉const
常量的定義,全部連起來吧
(fn =>
(f => f(f))(f => fn(n => f(f)(n)))
)(g =>
n => [1, 2].indexOf(n) > -1 ? 1 : g(n - 1) + g(n - 2)
)(10);
拆解這段代碼挺燒腦,膜拜一下代碼的作者。
雖然想不出有什麼用,但是很有趣,有趣就值得研究:D
Code For Fun!