建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
譯者按:程序員應(yīng)該知道遞歸，但是你真的知道是怎么回事么？
成都創(chuàng)新互聯(lián)公司是專(zhuān)業(yè)的泉州網(wǎng)站建設(shè)公司，泉州接單;提供網(wǎng)站制作、成都做網(wǎng)站,網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專(zhuān)業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行泉州網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專(zhuān)業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專(zhuān)業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!
- 原文: All About Recursion, PTC, TCO and STC in JavaScript
- 譯者: Fundebug
為了保證可讀性，本文采用意譯而非直譯。
遞歸簡(jiǎn)介
一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。
我們來(lái)舉個(gè)例子，我們可以用4的階乘乘以4來(lái)定義5的階乘，3的階乘乘以4來(lái)定義4的階乘，以此類(lèi)推。
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)開(kāi)始，一直遞歸調(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)用依賴(lài)factorial(0)
factorial(2) // 該調(diào)用依賴(lài)factorial(1)
factorial(3) // 該掉用依賴(lài)factorial(2)現(xiàn)在我們修改代碼，插入console.trace()來(lái)查看每一次當(dāng)前的調(diào)用棧的狀態(tài)：
function factorial(n) {
console.trace()
if (n === 0) {
return 1
}
return n * factorial(n - 1)
}
factorial(3)接下來(lái)我們看看調(diào)用棧是怎樣的。
第一個(gè)：
Trace
at factorial (repl:2:9)
at repl:1:1 // 請(qǐng)忽略以下底層實(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)。接下來(lái)就更加有趣了，我們來(lái)看第二次打印出來(lái)的調(diào)用棧：
Trace
at factorial (repl:2:9)
at factorial (repl:7:12)
at repl:1:1 // 請(qǐng)忽略以下底層實(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è)問(wèn)題呢？使用尾遞歸。
尾遞歸
尾遞歸是一種遞歸的寫(xiě)法，可以避免不斷的將函數(shù)壓棧最終導(dǎo)致堆棧溢出。通過(guò)設(shè)置一個(gè)累加參數(shù)，并且每一次都將當(dāng)前的值累加上去，然后遞歸調(diào)用。
我們來(lái)看如何改寫(xiě)之前定義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)用都不在依賴(lài)于上一個(gè)遞歸調(diào)用的值。因此，空間的復(fù)雜度為o(1)而不是0(n)。
接下來(lái)，通過(guò)console.trace()函數(shù)將調(diào)用棧打印出來(lái)。
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)
at factorial (repl:7:8)
at factorial (repl:7:8)
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:8)
at factorial (repl:7:8)
at factorial (repl:7:8)
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)這是為什么呢？
在Nodejs下面，我們可以通過(guò)開(kāi)啟strict mode, 并且使用--harmony_tailcalls來(lái)開(kāi)啟尾遞歸(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ì)變慢。不過(guò)，尾遞歸可以讓你使用更少的內(nèi)存，使你的遞歸函數(shù)更加安全 (前提是你要開(kāi)啟harmony模式)。
那么，博主這里就疑問(wèn)了：為什么尾遞歸一定要開(kāi)啟harmony模式才可以呢？
關(guān)于Fundebug
Fundebug專(zhuān)注于JavaScript、微信小程序、微信小游戲、支付寶小程序、React Native、Node.js和Java實(shí)時(shí)BUG監(jiān)控。 自從2016年雙十一正式上線(xiàn)，F(xiàn)undebug累計(jì)處理了7億+錯(cuò)誤事件，得到了Google、360、金山軟件、百姓網(wǎng)等眾多知名用戶(hù)的認(rèn)可。歡迎免費(fèi)試用！
版權(quán)聲明
轉(zhuǎn)載時(shí)請(qǐng)注明作者Fundebug以及本文地址：
https://blog.fundebug.com/2017/06/14/all-about-recursions/
本文名稱(chēng)：JavaScript中的遞歸
標(biāo)題鏈接：http://fisionsoft.com.cn/article/gieipe.html
