Fundebug

## 递归简介

``````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
``````

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

### 递归的调用栈

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

return n * factorial(n - 1)
}
``````

``````factorial(0) // 0的阶乘为1
factorial(1) // 该调用依赖factorial(0)
factorial(2) // 该调用依赖factorial(1)
factorial(3) // 该掉用依赖factorial(2)
``````

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

return n * factorial(n - 1)
}

factorial(3)
``````

``````Trace
at factorial (repl:2:9)
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)
at REPLServer.onLine (repl.js:513:10)
at emitOne (events.js:101:20)
``````

``````Trace
at factorial (repl:2:9)
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)
at REPLServer.onLine (repl.js:513:10)
``````

``````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)
``````

### 尾递归

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

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

`factorial(3)`的执行步骤如下：

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

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

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

factorial(3)
``````

``````// ...
// 下面是最后两次对factorial的调用
Trace
at factorial (repl:2:9) // 3次压栈
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)
``````

``````'use strict'

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

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

factorial(3)
``````

``````node --harmony_tailcalls factorial.js
``````

``````Trace
at factorial (/Users/stefanzan/factorial.js:3:13)
at Object.<anonymous> (/Users/stefanzan/factorial.js:9:1)
at Module._compile (module.js:570:32)
at Object.Module._extensions..js (module.js:579:10)
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.<anonymous> (/Users/stefanzan/factorial.js:9:1)
at Module._compile (module.js:570:32)
at Object.Module._extensions..js (module.js:579:10)
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.<anonymous> (/Users/stefanzan/factorial.js:9:1)
at Module._compile (module.js:570:32)
at Object.Module._extensions..js (module.js:579:10)
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.<anonymous> (/Users/stefanzan/factorial.js:9:1)
at Module._compile (module.js:570:32)
at Object.Module._extensions..js (module.js:579:10)
at Module.runMain (module.js:604:10)
at run (bootstrap_node.js:394:7)
at startup (bootstrap_node.js:149:9)
``````

### Fundebug

JavaScript专题之递归

JavaScript 专题系列第十八篇，讲解递归和尾递归 定义 程序调用自身的编程技巧称为递归(recursion)。 阶乘 以阶乘为例： 示意图(图片来自 wwww.penjee.com)： 斐波那契数列 在《JavaScript专...

2017/09/13
0
0

Fundebug
2018/10/30
0
0
JavaScript开发者应懂的33个概念

2018/10/22
0
0

oschina
2017/12/13
3.6K
0

hankzhuo
2018/10/26
0
0

Python爬虫也能用手机进行抓包？没错！这个技巧我只告诉你

11分钟前
0
0

Java面经
14分钟前
2
0
influxdb 学习

InfluxDB 学习 安装 brew install influxdb 启动 influxd -config /usr/local/etc/influxdb.conf 入门 \$ influx -precision rfc3339Connected to http://localhost:8086 version 1.2.xI......

solate
20分钟前
1
0

1 mongoDB索引的管理 　　 　　2 mongoDB中常用的索引类型 　　 　　1 单键索引 　　 　　2 复合索引 　　 　　3 多键索引 　　 　　4 哈希索引 　　 　　3 mongoDB中常用的索引属性 　　...

SEOwhywhy
21分钟前
0
0
JackJson中自定义JsonSerializer的使用

Coder顾
23分钟前
1
0