前言

這篇文章一個多月前以英文發表在我的個人博客，現在抽空翻譯成中文，并補充一些沒來得及寫的內容。

昨天我發表的《如何在 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 函數中定義了比較兩個值，并把大的值返回出去這個行為了。我們只需要把這同一個行為作用于尾部列表，程序會幫我們找到。