還不懂遞歸？讀完這篇文章保證你會懂
前言
創新互聯專注為客戶提供全方位的互聯網綜合服務，包含不限于成都做網站、成都網站建設、隆德網絡推廣、重慶小程序開發公司、隆德網絡營銷、隆德企業策劃、隆德品牌公關、搜索引擎seo、人物專訪、企業宣傳片、企業代運營等，從售前售中售后，我們都將竭誠為您服務，您的肯定，是我們最大的嘉獎；創新互聯為所有大學生創業者提供隆德建站搭建服務，24小時服務熱線：13518219792，官方網址：www.kartarina.com
這篇文章一個多月前以英文發表在我的個人博客，現在抽空翻譯成中文，并補充一些沒來得及寫的內容。
昨天我發表的《如何在 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 的過程中感受更多的是人類智力的不可思議和計算機科學中體現的普遍認識論規律。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對創新互聯的支持。
當前題目：還不懂遞歸？讀完這篇文章保證你會懂
URL分享：http://www.kartarina.com/article40/igcdho.html
成都網站建設公司_創新互聯，為您提供品牌網站設計、響應式網站、網站排名、網站設計、自適應網站、企業建站
聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯
- 教你如何做好網站策劃 2016-11-04
- 策劃的定義是什么，又該如何理解網站策劃？ 2022-06-21
- 中小企業做網站,網站策劃先行 2016-11-03
- 中小型企業網站建設出具網站策劃書包括哪些內容 2016-09-10
- 網站策劃在企業網站的建設中越來越重視 2022-09-22
- 網站策劃的重要性 2016-08-29
- 淺談網站策劃前期工作 2016-11-04
- 網站建設應該怎樣做好網站策劃？ 2014-01-26
- 企業做網站建設什么情況下寫網站策劃書？ 2016-10-13
- 學校網站建設_大學網站策劃_職業教育網站定制設計 2023-02-07
- 淺談網站策劃 2016-11-12
- 旅游網站策劃書 2021-10-07