国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JavaScript中的遞歸

Jacendfeng / 3011人閱讀

摘要：第三次第四次設(shè)想，如果傳入的參數(shù)值特別大，那么這個(gè)調(diào)用棧將會(huì)非常之大，最終可能超出調(diào)用棧的緩存大小而崩潰導(dǎo)致程序執(zhí)行失敗。注意尾遞歸不一定會(huì)將你的代碼執(zhí)行速度提高相反，可能會(huì)變慢。

譯者按: 程序員應(yīng)該知道遞歸，但是你真的知道是怎么回事么？

原文: All About Recursion, PTC, TCO and STC in JavaScript

譯者: Fundebug

為了保證可讀性，本文采用意譯而非直譯。

遞歸簡介 
一個(gè)過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。

我們來舉個(gè)例子，我們可以用4的階乘乘以4來定義5的階乘，3的階乘乘以4來定義4的階乘，以此類推。

factorial(5) = factorial(4) * 5
factorial(5) = factorial(3) * 4 * 5
factorial(5) = factorial(2) * 3 * 4 * 5
factorial(5) = factorial(1) * 2 * 3 * 4 * 5
factorial(5) = factorial(0) * 1 * 2 * 3 * 4 * 5
factorial(5) = 1 * 1 * 2 * 3 * 4 * 5

用Haskell的Pattern matching 可以很直觀的定義factorial函數(shù):

factorial n = factorial (n-1)  * n
factorial 0 = 1

在遞歸的例子中，從第一個(gè)調(diào)用factorial(5)開始，一直遞歸調(diào)用factorial函數(shù)自身直到參數(shù)的值為0。下面是一個(gè)形象的圖例：

遞歸的調(diào)用棧

為了理解調(diào)用棧，我們回到factorial函數(shù)的例子。

function factorial(n) {
    if (n === 0) {
        return 1
    }

    return n * factorial(n - 1)
}

如果我們傳入?yún)?shù)3，將會(huì)遞歸調(diào)用factorial(2)、factorial(1)和factorial(0)，因此會(huì)額外再調(diào)用factorial三次。

每次函數(shù)調(diào)用都會(huì)壓入調(diào)用棧，整個(gè)調(diào)用棧如下:

factorial(0) // 0的階乘為1 
factorial(1) // 該調(diào)用依賴factorial(0)
factorial(2) // 該調(diào)用依賴factorial(1)
factorial(3) // 該掉用依賴factorial(2)

現(xiàn)在我們修改代碼，插入console.trace()來查看每一次當(dāng)前的調(diào)用棧的狀態(tài)：

function factorial(n) {
    console.trace()
    if (n === 0) {
        return 1
    }

    return n * factorial(n - 1)
}

factorial(3)

接下來我們看看調(diào)用棧是怎樣的。
第一個(gè)：

Trace
    at factorial (repl:2:9)
    at repl:1:1 // 請忽略以下底層實(shí)現(xiàn)細(xì)節(jié)代碼
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)
    at emitOne (events.js:101:20)

你會(huì)發(fā)現(xiàn)，該調(diào)用棧包含一個(gè)對(duì)factorial函數(shù)的調(diào)用，這里是factorial(3)。接下來就更加有趣了，我們來看第二次打印出來的調(diào)用棧：

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at repl:1:1 // 請忽略以下底層實(shí)現(xiàn)細(xì)節(jié)代碼
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
    at REPLServer.onLine (repl.js:513:10)

現(xiàn)在我們有兩個(gè)對(duì)factorial函數(shù)的調(diào)用。

第三次：

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)

第四次：

Trace
    at factorial (repl:2:9)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at factorial (repl:7:12)
    at repl:1:1
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)

設(shè)想，如果傳入的參數(shù)值特別大，那么這個(gè)調(diào)用棧將會(huì)非常之大，最終可能超出調(diào)用棧的緩存大小而崩潰導(dǎo)致程序執(zhí)行失敗。那么如何解決這個(gè)問題呢？使用尾遞歸。

尾遞歸

尾遞歸是一種遞歸的寫法，可以避免不斷的將函數(shù)壓棧最終導(dǎo)致堆棧溢出。通過設(shè)置一個(gè)累加參數(shù)，并且每一次都將當(dāng)前的值累加上去，然后遞歸調(diào)用。

我們來看如何改寫之前定義factorial函數(shù)為尾遞歸：

function factorial(n, total = 1) {
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}

factorial(3)的執(zhí)行步驟如下：

factorial(3, 1) 
factorial(2, 3) 
factorial(1, 6) 
factorial(0, 6)

調(diào)用棧不再需要多次對(duì)factorial進(jìn)行壓棧處理，因?yàn)槊恳粋€(gè)遞歸調(diào)用都不在依賴于上一個(gè)遞歸調(diào)用的值。因此，空間的復(fù)雜度為o(1)而不是0(n)。

接下來，通過console.trace()函數(shù)將調(diào)用棧打印出來。

function factorial(n, total = 1) {
    console.trace()
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}

factorial(3)

很驚訝的發(fā)現(xiàn)，依然有很多壓棧!

// ...
// 下面是最后兩次對(duì)factorial的調(diào)用
Trace
    at factorial (repl:2:9) // 3次壓棧
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at repl:1:1 // 請忽略以下底層實(shí)現(xiàn)細(xì)節(jié)代碼
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)
    at REPLServer.runBound [as eval] (domain.js:293:12)
Trace
    at factorial (repl:2:9) // 最后第一調(diào)用再次壓棧
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at factorial (repl:7:8)
    at repl:1:1 // 請忽略以下底層實(shí)現(xiàn)細(xì)節(jié)代碼
    at realRunInThisContextScript (vm.js:22:35)
    at sigintHandlersWrap (vm.js:98:12)
    at ContextifyScript.Script.runInThisContext (vm.js:24:12)
    at REPLServer.defaultEval (repl.js:313:29)
    at bound (domain.js:280:14)

這是為什么呢？
在Nodejs下面，我們可以通過開啟strict mode, 并且使用--harmony_tailcalls來開啟尾遞歸(proper tail call)。

"use strict"

function factorial(n, total = 1) {
    console.trace()
    if (n === 0) {
        return total
    }

    return factorial(n - 1, n * total)
}

factorial(3)

使用如下命令：

node --harmony_tailcalls factorial.js

調(diào)用棧信息如下：

Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object. (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object. (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object. (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)
Trace
    at factorial (/Users/stefanzan/factorial.js:3:13)
    at Object. (/Users/stefanzan/factorial.js:9:1)
    at Module._compile (module.js:570:32)
    at Object.Module._extensions..js (module.js:579:10)
    at Module.load (module.js:487:32)
    at tryModuleLoad (module.js:446:12)
    at Function.Module._load (module.js:438:3)
    at Module.runMain (module.js:604:10)
    at run (bootstrap_node.js:394:7)
    at startup (bootstrap_node.js:149:9)

你會(huì)發(fā)現(xiàn)，不會(huì)在每次調(diào)用的時(shí)候壓棧，只有一個(gè)factorial。

注意：尾遞歸不一定會(huì)將你的代碼執(zhí)行速度提高；相反，可能會(huì)變慢。不過，尾遞歸可以讓你使用更少的內(nèi)存，使你的遞歸函數(shù)更加安全 (前提是你要開啟harmony模式)。

那么，博主這里就疑問了：為什么尾遞歸一定要開啟harmony模式才可以呢？ 歡迎各位留言討論。

關(guān)于Fundebug

Fundebug專注于JavaScript、微信小程序、微信小游戲、支付寶小程序、React Native、Node.js和Java線上應(yīng)用實(shí)時(shí)BUG監(jiān)控。 自從2016年雙十一正式上線，F(xiàn)undebug累計(jì)處理了9億+錯(cuò)誤事件，付費(fèi)客戶有Google、360、金山軟件、百姓網(wǎng)等眾多品牌企業(yè)。歡迎大家免費(fèi)試用！

版權(quán)聲明

轉(zhuǎn)載時(shí)請注明作者Fundebug以及本文地址：
https://blog.fundebug.com/2017/06/14/all-about-recursions/

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/83572.html

相關(guān)文章

  • javascript中的遞歸

    摘要：二項(xiàng)目中用到的幾個(gè)經(jīng)典的遞歸求的和分析假設(shè)遞歸函數(shù)已經(jīng)寫好為，即，就是求的和。遞歸函數(shù)實(shí)現(xiàn)每天凌晨定時(shí)啟動(dòng)定時(shí)器執(zhí)行代碼分析假設(shè)遞歸函數(shù)已經(jīng)寫好了。 一、遞歸的概念 在程序中函數(shù)直接或者間接調(diào)用自身的一種方法，就叫做遞歸。它通常把一個(gè)大型復(fù)雜的問題轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程中所需要的多次重復(fù)計(jì)算，大大減少了程序的代碼了。 二、...

    acrazing 評(píng)論0 收藏0

  • JavaScript專題之遞歸

    摘要：專題系列第十八篇，講解遞歸和尾遞歸定義程序調(diào)用自身的編程技巧稱為遞歸。然而非尾調(diào)用函數(shù)，就會(huì)創(chuàng)建多個(gè)執(zhí)行上下文壓入執(zhí)行上下文棧。所以我們只用把階乘函數(shù)改造成一個(gè)尾遞歸形式，就可以避免創(chuàng)建那么多的執(zhí)行上下文。 JavaScript 專題系列第十八篇，講解遞歸和尾遞歸 定義 程序調(diào)用自身的編程技巧稱為遞歸(recursion)。 階乘 以階乘為例： function factorial(n...

    asoren 評(píng)論0 收藏0

  • ES6函數(shù)與Lambda演算

    摘要：高階函數(shù)函數(shù)式編程中，接受函數(shù)作為參數(shù)，或者返回一個(gè)函數(shù)作為結(jié)果的函數(shù)通常就被稱為高階函數(shù)。均屬于高階函數(shù)，高階函數(shù)并不神秘，我們?nèi)粘＞幊桃矔?huì)用到。參考演算函數(shù)式編程指南入門康托爾哥德爾圖靈永恒的金色對(duì)角線原文函數(shù)與演算 緣起 造了一個(gè)輪子，根據(jù)GitHub項(xiàng)目地址，生成項(xiàng)目目錄樹，直觀的展現(xiàn)項(xiàng)目結(jié)構(gòu)，以便于介紹項(xiàng)目。歡迎Star。 repository-tree 技術(shù)棧： ES6 ...

    fasss 評(píng)論0 收藏0

  • 翻譯連載 | 第 9 章：遞歸（上）－《JavaScript輕量級(jí)函數(shù)式編程》 |《你不知道的JS》

    摘要：一旦我們滿足了基本條件值為，我們將不再調(diào)用遞歸函數(shù)，只是有效地執(zhí)行了。遞歸深諳函數(shù)式編程之精髓，最被廣泛引證的原因是，在調(diào)用棧中，遞歸把大部分顯式狀態(tài)跟蹤換為了隱式狀態(tài)。 原文地址：Functional-Light-JS 原文作者：Kyle Simpson－《You-Dont-Know-JS》作者 關(guān)于譯者：這是一個(gè)流淌著滬江血液的純粹工程：認(rèn)真，是 HTML 最堅(jiān)實(shí)的梁柱；...

    MasonEast 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)和算法類面試題javascript代碼實(shí)現(xiàn)

    摘要：正文面試題重建二叉樹題目輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。前序遍歷序列為，中序遍歷序列，。確定了左右子樹后遞歸處理。方法方法面試題在時(shí)間刪除鏈表結(jié)點(diǎn)。 寫在前面 本文的題目均來自于劍指offer中的題目，題目序號(hào)保持了書中的題目序號(hào)，由于某些題目并不適合于javascript這種語言，所以這些題目就沒有寫在本篇博客中，因此會(huì)出現(xiàn)題目序號(hào)的中斷。 正文 面試題6：...

    Dean 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<