前言
這篇文章一個多月前以英文發表在我的個人博客，現在抽空翻譯成中文，并補充一些沒來得及寫的內容。
昨天我發表的《如何在 JS 代碼中消滅 for 循環》引起很多爭議。為了避免沒營養的討論，我先聲明一下。遞歸性能差是沒爭議的事實，如果你覺得 for 循環更好，沒必要學遞歸，那看到這里你可以不用看了。這篇文章要展示的大部分代碼，僅僅是學習目的，我不推薦在生產環境中用。但是如果你對函數式編程感興趣，想深入理解一些核心概念，你應該讀下去。
今年年初我開始學 Haskell 的時候，我被函數式代碼的優雅和簡潔俘獲了。代碼居然還能這樣寫！用指令式代碼要寫一堆的程序，用遞歸幾行就解決了。這篇文章里，我會把我在 Haskell 里面看到的遞歸函數翻譯成 JS 和 Python，并盡量每一步解釋。最后我會嘗試解決遞歸爆棧（Stack Overflow）的問題。
遞歸基礎
我從 Python 代碼開始，然后展示 JS 實現。
很多解釋遞歸的教程是從解釋斐波那契數列開始的，我覺得這樣做是在用一個已經復雜的概念去解釋另一個復雜的概念，沒有必要。我們還是從簡單的代碼開始吧。
運行這段 Python 代碼：
def foo(): foo()foo()
當然會報錯。😱 foo 函數會一直調用自己。因為我沒有告訴它何時停，它會一直執行下去，直到爆棧。那我們稍作修改再運行一下：
def foo(n): if n <= 1: return foo(n-1)foo(10)
這段代碼基本什么都沒做，但是這次它不會報錯了。我在 foo 函數定義初始就告訴它什么時候該停，然后我每次調用的時候都把參數改一下，直到參數滿足判斷條件，函數停止執行。
如果你理解了上面兩段代碼，你已經理解遞歸了。
從上面的代碼我總結一下遞歸的核心構成：
現在我們來用 Python 寫個 max 函數，找出列表中的最大值。是的，我知道 Python 原生有 max 函數，我重新發明個輪子只是為了學習和好玩。
# 不要用這個函數，還是用原生的 max 吧。def max2(list): if len(list) == 1: return list[0] head, tail = list[0], list[1:] return head if head > max2(tail) else max2(tail)print max2([3,98,345])# 345
max2函數接受一個列表作為參數，如果列表長度為 1，函數停止執行并把列表第一個元素返回出去。注意，當遞歸停止時，它必須返回值。（但是如果你想用遞歸去執行副作用，而不是純計算的話，可以不返回值。）如果初始判斷條件不滿足，把列表的頭和尾取出來。接著，我們比較頭部元素和尾部列表中最大值的大?。ㄎ覀兿炔还芪膊苛斜碇凶畲笾凳悄膫€），并把比較結果中更大的那個值返回出去。那我們怎樣知道尾部列表中的最大值？答案是我們不用知道。我們已經在 max2 函數中定義了比較兩個值，并把大的值返回出去這個行為了。我們只需要把這同一個行為作用于尾部列表，程序會幫我們找到。
下面是 JS 的實現：
const max = xs => { if (xs.length === 1) return xs[0]; const [head, ...tail] = xs; return head > max(tail) ? head : max(tail);};更多遞歸的例子
接下來我展示幾個我從 Haskell 翻譯過來的遞歸函數。剛剛已經用很大篇幅解釋遞歸了，這些函數就不解釋了。
reverse
Python 版：
# Python 內置有 reverse 函數def reverse2(list): if len(list) == 1: return list head, tail = list[0], list[1:] return reverse2(tail) + [x]print reverse2([1,2,3,4,5,6])# [6,5,4,3,2,1]
JS 版：
const reverse = xs => { if (xs.length === 1) return xs; const [head, ...tail] = xs; return reverse(tail).concat(head);};map
Python 版：
# Python 內置有 map 函數def map2(f, list): if len(list) == 0: return [] head, tail = list[0], list[1:] return [f(head)] + map2(f, tail)print map2(lambda x : x + 1, [2,2,2,2])# [3,3,3,3]
JS 版：
const map = f => xs => { if (xs.length === 0) return []; const [head, ...tail] = xs; return [f(head), ...map(f)(tail)];};zipWith
zipWith 接受一個回調函數和兩個列表為參數。他會并行遍歷兩個列表，并把單遍歷到的元素一一對應，傳進回調函數，把每一步遍歷的計算結果存在新的列表里，最終返回這個心列表。
Python 版：
def zipWith(f, listA, listB): if len(listA) == 0 or len(listB) == 0: return [] headA, tailA = listA[0], listA[1:] headB, tailB = listB[0], listB[1:] return [f(headA, headB)] + zipWith(f, tailA, tailB)print zipWith(lambda x, y : x + y, [2,2,2,2], [3,3,3,3,3])# [5,5,5,5]# 結果列表長度由參數中兩個列表更短的那個決定
JS 版：
const zipWith = f => xs => ys => { if (xs.length === 0 || ys.length === 0) return []; const [headX, ...tailX] = xs; const [headY, ...tailY] = ys; return [f(headX)(headY), ...zipWith(f)(tailX)(tailY)];};replicate
Python 版：
def replicate(n,x): if n <= 0: return [] return [x] + replicate(n-1,x)print replicate(4, 'hello')# ['hello', 'hello', 'hello', 'hello']
JS 版：
const replicate = (n, x) => { if (n <= 0) return []; return [x, ...replicate(n - 1, x)];};reduce
Python 不鼓勵用 reduce，我就不寫了。
JS 版：
const reduce = (f, acc, arr) => { if (arr.length === 0) return acc; const [head, ...tail] = arr; return reduce(f, f(head, acc), tail);};quickSort
用遞歸來實現排序算法肯定不是最優的，但是如果處理數據量小的話，也不是不能用。
Python 版：
def quickSort(xs): if len(xs) <= 1: return xs pivot, rest = xs[0], xs[1:] smaller, bigger = [], [] for x in rest: smaller.append(x) if x < pivot else bigger.append(x) return quickSort(smaller) + [pivot] + quickSort(bigger)print quickSort([44,14,65,34])# [14, 34, 44, 65]
JS 版：
const quickSort = list => { if (list.length === 0) return list; const [pivot, ...rest] = list; const smaller = []; const bigger = []; rest.forEach(x => x < pivot ? smaller.push(x) : bigger.push(x); ); return [...quickSort(smaller), pivot, ...quickSort(bigger)]};解決遞歸爆棧問題
由于我對 Python 還不是特別熟，這個問題只講 JS 場景了，抱歉。
每次遞歸時，JS 引擎都會生成新的 frame 分配給當前執行函數，當遞歸層次太深時，可能會棧不夠用，導致爆棧。ES6引入了尾部優化（TCO），即當遞歸處于尾部調用時，JS 引擎會把每次遞歸的函數放在同一個 frame 里面，不新增 frame，這樣就解決了爆棧問題。
然而，V8 引擎在短暫支持 TCO 之后，放棄支持了。那為了避免爆棧，我們只能在程序層面解決問題了。 為了解決這個問題，大神們發明出了 trampoline 這個函數。來看代碼：
const trampoline = fn => (...args) => { let result = fn(...args); while (typeof result === "function") { result = result(); } return result;};給trampoline傳個遞歸函數，它會把遞歸函數的每次遞歸計算結果保存下來，然后只要遞歸沒結束，它就不停執行每次遞歸返回的函數。這樣做相當于把多次的函數調用放到一次函數調用里了，不會新增 frame，當然也不會爆棧。
先別高興太早。仔細看 trampoline 函數的話，你會發現它也要求傳入的遞歸函數符合尾部調用的情況。那不符合尾部調用的遞歸函數怎么辦呢？（ 比如我剛剛寫的 JS 版 quickSort，最后 return 的結果里，把兩個遞歸調用放在了一個結果里。這種情況叫 binary recursion，暫譯二元遞歸，翻譯錯了勿怪 ）
這個問題我也糾結了很久了，然后直接去 Stack Overflow 問了，然后真有大神回答了。要解決把二元遞歸轉換成尾部調用，需要用到一種叫 Continuous Passing Style (CPS) 的技巧。來看怎么把 quickSort 轉成尾部調用:
const identity = x => x;const quickSort = (list, cont = identity) => { if (list.length === 0) return cont(list); const [pivot, ...rest] = list; const smaller = []; const bigger = []; rest.forEach(x => (x < pivot ? smaller.push(x) : bigger.push(x))); return quickSort(smaller, a => quickSort(bigger, b => cont([...a, pivot, ...b])), );};tramploline(quickSort)([5, 1, 4, 3, 2]) // -> [1, 2, 3, 4, 5]如果上面的寫法難以理解，推薦去看 Kyle Simpson 的這章內容。我不能保證比他講的更清楚，就不講了。
屠龍之技
雖然我將要講的這個概念在 JS 中根本都用不到，但是我覺得很好玩，就加進來了。有些編程語言是不支持遞歸的（我本科不是學的計算機，不知道是哪些語言），那這時候如果我知道用遞歸可以解決某個問題，該怎么辦？用 Y-combinator.
JS 實現：
function y(le) { return (function(f) { return f(f); })(function(f) { return le(function(x) { return f(f)(x); }); });}const factorial = y(function(fac) { return function(n) { return n <= 2 ? n : n * fac(n - 1); };});factorial(5); // 120factorial函數不用遞歸實現了遞歸。
展示這段代碼不是為了炫技。這根本不是我寫的代碼，是我從 Douglas Crockford （《JS 語言精髓》的作者）的課程里學到的?？吹竭@段代碼時我感到很激動，驚嘆計算機科學的精妙和優雅。很多人把程序員職業當做是搬磚的，但是我不這么看。我在學習 CS 的過程中感受更多的是人類智力的不可思議和計算機科學中體現的普遍認識論規律。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對武林網的支持。
新聞熱點
疑難解答
