還不懂遞歸？讀完這篇文章保證你會(huì)懂

前言

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

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

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

遞歸基礎(chǔ)

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

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

運(yùn)行這段 Python 代碼：

def foo():
 foo()

foo()

當(dāng)然會(huì)報(bào)錯(cuò)。😱 foo 函數(shù)會(huì)一直調(diào)用自己。因?yàn)槲覜]有告訴它何時(shí)停，它會(huì)一直執(zhí)行下去，直到爆棧。那我們稍作修改再運(yùn)行一下：

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

foo(10)

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

如果你理解了上面兩段代碼，你已經(jīng)理解遞歸了。

從上面的代碼我總結(jié)一下遞歸的核心構(gòu)成：

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

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

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

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

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

更多遞歸的例子

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

reverse

Python 版：

# Python 內(nèi)置有 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 內(nèi)置有 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 接受一個(gè)回調(diào)函數(shù)和兩個(gè)列表為參數(shù)。他會(huì)并行遍歷兩個(gè)列表，并把單遍歷到的元素一一對(duì)應(yīng)，傳進(jìn)回調(diào)函數(shù)，把每一步遍歷的計(jì)算結(jié)果存在新的列表里，最終返回這個(gè)心列表。

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

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 不鼓勵(lì)用 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

用遞歸來實(shí)現(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)]
};

解決遞歸爆棧問題

由于我對(duì) Python 還不是特別熟，這個(gè)問題只講 JS 場(chǎng)景了，抱歉。

每次遞歸時(shí)，JS 引擎都會(huì)生成新的 frame 分配給當(dāng)前執(zhí)行函數(shù)，當(dāng)遞歸層次太深時(shí)，可能會(huì)棧不夠用，導(dǎo)致爆棧。ES6引入了尾部?jī)?yōu)化（TCO），即當(dāng)遞歸處于尾部調(diào)用時(shí)，JS 引擎會(huì)把每次遞歸的函數(shù)放在同一個(gè) frame 里面，不新增 frame，這樣就解決了爆棧問題。

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

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

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

先別高興太早。仔細(xì)看 trampoline 函數(shù)的話，你會(huì)發(fā)現(xiàn)它也要求傳入的遞歸函數(shù)符合尾部調(diào)用的情況。那不符合尾部調(diào)用的遞歸函數(shù)怎么辦呢？（ 比如我剛剛寫的 JS 版 quickSort，最后 return 的結(jié)果里，把兩個(gè)遞歸調(diào)用放在了一個(gè)結(jié)果里。這種情況叫 binary recursion，暫譯二元遞歸，翻譯錯(cuò)了勿怪 ）

這個(gè)問題我也糾結(jié)了很久了，然后直接去 Stack Overflow 問了，然后真有大神回答了。要解決把二元遞歸轉(zhuǎn)換成尾部調(diào)用，需要用到一種叫 Continuous Passing Style (CPS) 的技巧。來看怎么把 quickSort 轉(zhuǎn)成尾部調(diào)用:

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 的這章內(nèi)容。我不能保證比他講的更清楚，就不講了。

屠龍之技

雖然我將要講的這個(gè)概念在 JS 中根本都用不到，但是我覺得很好玩，就加進(jìn)來了。有些編程語(yǔ)言是不支持遞歸的（我本科不是學(xué)的計(jì)算機(jī)，不知道是哪些語(yǔ)言），那這時(shí)候如果我知道用遞歸可以解決某個(gè)問題，該怎么辦？用 Y-combinator.

JS 實(shí)現(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ù)不用遞歸實(shí)現(xiàn)了遞歸。

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

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問大家可以留言交流，謝謝大家對(duì)億速云的支持。