口水仗系列：recursion vs. for-loop

充滿萌新的編程圈子的日常之一就是經常群魔亂舞地討論一些無謂的問題，這個肯定大家見得多了：

到底我寫代碼用 recursion 還是 for-loop 好啊？

然後就開始鼓搗出各種結論來，不過由於自身姿勢水平太低，又討論不出甚麼名堂，結果就是這樣的：

A: 當然是f or-loop 快啊，你看看我這用5分鐘時間拼出來的 JSPerf，一個空迴圈裡面可是快了 10%

B: 別用 recursion 啊，會爆棧的，就像

function triangularSum(n) {return n>0 ? n+triangularSum(n-1) : 0}

你跑個 triangularSum(20000) 就出來 call stack overflow 了，反觀 for-loop 就沒有這個問題

C: 又想 recursion 又想不爆棧的話只能 tco 了，不過咱們語言不支援 tco，你死心吧

D: recursion 不是公認的慢到死嘛，例如

function fib(n) {return n<2 ? 1 : fib(n-2)+fib(n-1);}

你試著跑 fib(50)，等到下個月都沒跑出結果來呢，相比之下

function fib(n) { var a=1; b=1; for(let i=0; i<n; i++) { let temp = b; b = a+b; a = temp; } return a;}

就可以秒出結果，這還不說明 recursion 辣雞

E: 說個啥啊，簡單來說就是 recursion 只有一個好就是短，其他都比 for-loop 差，實用代碼裡誰用 recursion 打死誰

我看到這些只能說啊，你們還要學習一個，不要甚麼都不懂就在指點江山，把別人批判一番。

為甚麼？因為 for-loop 和 recursion 是抽象程度完全不一樣的東西，拿起來平行對比就是 comparing apples to oranges，就像你說所有語言都跑得比 C 慢所以沒 C 好一樣，naive。

for-loop 是一種非常 low-level 的構造，就比 label/goto （一段小代碼再在結尾加個 conditional jump 跳回去前面）高那麼一點點。

recursion 是一個抽象概念，沒有實現可言（事實上可以有多種實現）。

兩個等級都不一樣，你比個卵呢？

你真要把兩個相比的話，那麼請把 for-loop 換成 foreach-loop/list comprehension/first-class array 方法（map/filter/fold），或者直接操作棧內容/用上 tco/trampoline/Wheeler jump 來實現 recursion。那麼大家抽象度就相等了，可以同台競技比較了。

當然大家也知道，當你這麼做之後，上述智障又會跟你說 list comprehension 和 first-class array 方法沒 for-loop 快，再丟你一個 JSPerf 說後者快 20% 云云的，人改不了智障就是如此。

這個涉及一個更普遍的問題，一個沒徹底了解語言構造的人經常犯的通病：拿不同抽象度和層次的東西直接平行比較。

再舉個例子，一般使用 for-loop 都是為了遍歷一個 index 去存取一個陣列的元素：

for(let i=0; i<arr.length; i++) { /*...*/ }

這個動作裡面又包含了一堆抽象度的問題：for-loop 以 index 存取陣列元素是 C 等 low-level 語言才是有意義的，它的意思是陣列是一堆 fixed-size 的元素，用數字存取就是把指針按元素大小往前演進。

但是極大部份高級語言根本不會這樣做，陣列根本不是 fixed-size 的（其實這還能叫陣列嗎），甚至可能根本不提供 index，所謂的 index 其實都是編出來讓你以為這是傳統陣列的 key，這樣的實現裡其實寫的根本不是 for-loop ，是 foreach-loop，把一個 collection 裡的元素遍歷一次：

for(let e of arr) { /*...*/ }

甚麼？你說你想同時有一個 index 去進行操作？ range + zipWith/enumerate 走起。

甚麼？你說你想以 index 存取要素？不存在的，都是摸擬出來的，有兩種方法，一種是 JS 的在 dict 裡創造 int32 的 key，另一種就是遞歸式的做法：

xs !! 0 = head xsxs !! n = (tail xs) !! n-1 -- 不考慮 n<0 的場合

for-loop + index 這套構造只能用來描述 fixed-size 陣列，在更抽象的 Collection 裡根本就沒有這種東西，對 Collection 進行操作的方式只有那麼幾種（foreach-loop/comprehension/first-class 方法），這裡根本就沒有 for-loop + index 的構造，就算有也是模擬出來的，何從比較呢？

問題本來就是 ill-defined 的，還在找一群人瞎討論，自然是口水仗。

以上的對於基本編程技巧的口水仗例子在編程圈裡可多著了，磬竹難書啊，都可以寫一個系列了。

這些東西呢，一般根本不會有人告訴你的，只有鍛鍊出明銳的洞察力和領悟力，才會看得出來。