前言

創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務，包含不限于成都做網(wǎng)站、成都網(wǎng)站建設、隆德網(wǎng)絡推廣、重慶小程序開發(fā)公司、隆德網(wǎng)絡營銷、隆德企業(yè)策劃、隆德品牌公關、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運營等，從售前售中售后，我們都將竭誠為您服務，您的肯定，是我們最大的嘉獎；創(chuàng)新互聯(lián)為所有大學生創(chuàng)業(yè)者提供隆德建站搭建服務，24小時服務熱線：13518219792，官方網(wǎng)址：www.cdcxhl.com

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

昨天我發(fā)表的《如何在 JS 代碼中消滅 for 循環(huán)》引起很多爭議。為了避免沒營養(yǎng)的討論，我先聲明一下。遞歸性能差是沒爭議的事實，如果你覺得 for 循環(huán)更好，沒必要學遞歸，那看到這里你可以不用看了。這篇文章要展示的大部分代碼，僅僅是學習目的，我不推薦在生產環(huán)境中用。但是如果你對函數(shù)式編程感興趣，想深入理解一些核心概念，你應該讀下去。

今年年初我開始學 Haskell 的時候，我被函數(shù)式代碼的優(yōu)雅和簡潔俘獲了。代碼居然還能這樣寫！用指令式代碼要寫一堆的程序，用遞歸幾行就解決了。這篇文章里，我會把我在 Haskell 里面看到的遞歸函數(shù)翻譯成 JS 和 Python，并盡量每一步解釋。最后我會嘗試解決遞歸爆棧（Stack Overflow）的問題。

遞歸基礎

我從 Python 代碼開始，然后展示 JS 實現(xiàn)。

很多解釋遞歸的教程是從解釋斐波那契數(shù)列開始的，我覺得這樣做是在用一個已經復雜的概念去解釋另一個復雜的概念，沒有必要。我們還是從簡單的代碼開始吧。

運行這段 Python 代碼：

def foo():
 foo()

foo()

當然會報錯。😱 foo 函數(shù)會一直調用自己。因為我沒有告訴它何時停，它會一直執(zhí)行下去，直到爆棧。那我們稍作修改再運行一下：

def foo(n):
 if n <= 1:
 return
 foo(n-1)

foo(10)

這段代碼基本什么都沒做，但是這次它不會報錯了。我在 foo 函數(shù)定義初始就告訴它什么時候該停，然后我每次調用的時候都把參數(shù)改一下，直到參數(shù)滿足判斷條件，函數(shù)停止執(zhí)行。

如果你理解了上面兩段代碼，你已經理解遞歸了。

從上面的代碼我總結一下遞歸的核心構成：

• 遞歸函數(shù)必須接受參數(shù)。
• 在遞歸函數(shù)的定義初始，應該有一個判斷條件，當參數(shù)滿足這個條件的時候，函數(shù)停止執(zhí)行，并返回值。
• 每次遞歸函數(shù)執(zhí)行自己的時候，都需要把當前參數(shù)做某種修改，然后傳入下一次遞歸。當參數(shù)被累積修改到符合初始判斷條件了，遞歸就停止了。

現(xiàn)在我們來用 Python 寫個 max 函數(shù)，找出列表中的最大值。是的，我知道 Python 原生有 max 函數(shù)，我重新發(fā)明個輪子只是為了學習和好玩。

# 不要用這個函數(shù)，還是用原生的 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函數(shù)接受一個列表作為參數(shù)，如果列表長度為 1，函數(shù)停止執(zhí)行并把列表第一個元素返回出去。注意，當遞歸停止時，它必須返回值。（但是如果你想用遞歸去執(zhí)行副作用，而不是純計算的話，可以不返回值。）如果初始判斷條件不滿足，把列表的頭和尾取出來。接著，我們比較頭部元素和尾部列表中最大值的大?。ㄎ覀兿炔还芪膊苛斜碇凶畲笾凳悄膫€），并把比較結果中更大的那個值返回出去。那我們怎樣知道尾部列表中的最大值？答案是我們不用知道。我們已經在 max2 函數(shù)中定義了比較兩個值，并把大的值返回出去這個行為了。我們只需要把這同一個行為作用于尾部列表，程序會幫我們找到。

下面是 JS 的實現(xiàn)：

const max = xs => {
 if (xs.length === 1) return xs[0];
 const [head, ...tail] = xs;
 return head > max(tail) ? head : max(tail);
};

更多遞歸的例子

接下來我展示幾個我從 Haskell 翻譯過來的遞歸函數(shù)。剛剛已經用很大篇幅解釋遞歸了，這些函數(shù)就不解釋了。

reverse

Python 版：

# Python 內置有 reverse 函數(shù)
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 函數(shù)
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 接受一個回調函數(shù)和兩個列表為參數(shù)。他會并行遍歷兩個列表，并把單遍歷到的元素一一對應，傳進回調函數(shù)，把每一步遍歷的計算結果存在新的列表里，最終返回這個心列表。

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]
# 結果列表長度由參數(shù)中兩個列表更短的那個決定

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

用遞歸來實現(xiàn)排序算法肯定不是最優(yōu)的，但是如果處理數(shù)據(jù)量小的話，也不是不能用。

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 分配給當前執(zhí)行函數(shù)，當遞歸層次太深時，可能會棧不夠用，導致爆棧。ES6引入了尾部優(yōu)化（TCO），即當遞歸處于尾部調用時，JS 引擎會把每次遞歸的函數(shù)放在同一個 frame 里面，不新增 frame，這樣就解決了爆棧問題。

然而，V8 引擎在短暫支持 TCO 之后，放棄支持了。那為了避免爆棧，我們只能在程序層面解決問題了。 為了解決這個問題，大神們發(fā)明出了 trampoline 這個函數(shù)。來看代碼：

const trampoline = fn => (...args) => {
 let result = fn(...args);
 while (typeof result === "function") {
 result = result();
 }
 return result;
};

給trampoline傳個遞歸函數(shù)，它會把遞歸函數(shù)的每次遞歸計算結果保存下來，然后只要遞歸沒結束，它就不停執(zhí)行每次遞歸返回的函數(shù)。這樣做相當于把多次的函數(shù)調用放到一次函數(shù)調用里了，不會新增 frame，當然也不會爆棧。

先別高興太早。仔細看 trampoline 函數(shù)的話，你會發(fā)現(xiàn)它也要求傳入的遞歸函數(shù)符合尾部調用的情況。那不符合尾部調用的遞歸函數(shù)怎么辦呢？（ 比如我剛剛寫的 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 實現(xiàn)：

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); // 120

factorial函數(shù)不用遞歸實現(xiàn)了遞歸。

展示這段代碼不是為了炫技。這根本不是我寫的代碼，是我從 Douglas Crockford （《JS 語言精髓》的作者）的課程里學到的。看到這段代碼時我感到很激動，驚嘆計算機科學的精妙和優(yōu)雅。很多人把程序員職業(yè)當做是搬磚的，但是我不這么看。我在學習 CS 的過程中感受更多的是人類智力的不可思議和計算機科學中體現(xiàn)的普遍認識論規(guī)律。

總結

以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對創(chuàng)新互聯(lián)的支持。