其他章节请看：
递归
递归的概念
递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。
递归通常涉及调用函数本身，直接调用自身，亦或者间接调用自身，都是递归函数。就像这样：
// 直接调用自身
function fn1(){
fn1()
}
// 间接调用自身
function fn2(){
fn3()
}
function fn3(){
fn2()
}
现在执行 fn1() 会一直执行下去，所以每个递归函数都必须有一个不在递归调用的条件（即基线条件），以防止无限递归。
有句名言：要理解递归，首先要理解递归。我们将其翻译成 javascript 代码：
<script>
function 理解递归() {
const answer = confirm('你理解递归了吗？')
if (answer) {
return
}
理解递归()
}
理解递归()
</script>
将这段代码在浏览器中执行，会不断询问 你理解递归了吗？，直到你点击 确认 才会终止。
计算一个数的阶乘
一个正整数的 阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!
亦即n!=1×2×3×...×(n-1)×n
5 的阶乘表示为 5!，等于 1*2*3*4*5，即 120
请看递归实现：
// 默认 n 是大于等于0的正整数
function factorial(n) {
// 基线条件
if (n <= 1) {
return 1
}
// 递归调用
return n * factorial(n - 1)
}
console.log(factorial(5)) // 120
超出最大调用堆栈大小
如果忘记给递归函数添加停止的条件，会发生什么？就像这样：
<script>
let i = 0
function fn4() {
i++
return fn4()
}
try {
fn4()
} catch (e) {
console.log(`i : ${i} error : ${e}`)
}
</script>
测试：
// Google Chrome v95
i : 13955 error : RangeError: Maximum call stack size exceeded
// Microsoft Edge v95
i : 13948 error : RangeError: Maximum call stack size exceeded
在 chrome v95 中，该函数执行了 13955 次，最后抛出错误：RangeError：超出最大调用堆栈大小，因此，具有停止递归的基线条件非常重要。
Tip：es6 有尾调用优化，也就是说这段代码会一直执行下去。查看 兼容表 你会发现绝大多数浏览器都不支持尾调用（proper tail calls (tail call optimisation)），故不在展开。
斐波那契数
斐波那契数列（Fibonacci sequence）指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……
数 2 由 1 + 1 得到，数 3 由 2 + 1 得到，数 5 由 3 + 2 得到，以此类推。
斐波拉契数列定义如下：
- 位置 0 的斐波拉契数是 0
- 位置 1 和 2 的斐波拉契数为 1
- 位置 n（此处 n > 2）的斐波拉契数是 (n - 1) 的斐波拉契数加上 (n - 2) 的斐波拉契数。
请看递归实现：
function fibonacci(val) {
if (val <= 1) {
return val
}
return fibonacci(val - 1) + fibonacci(val - 2)
}
// 0 1 1 2 3 5
for (let i = 0; i <= 5; i++) {
console.log(fibonacci(i))
}
递归更快吗
我们使用 console.time() 来检测两个版本的 fibonacci 函数（迭代实现 vs 递归实现）：
// 迭代求斐波拉契数
function fibonacciIterative(n) {
let pre = 1
let prePre = 0
let result = n
for (let i = 2; i <= n; i++) {
result = pre + prePre;
[prePre, pre] = [pre, pre + prePre]
}
return result
}
测试：
console.time('fibonacciIterative()')
console.log(fibonacciIterative(45))
console.timeEnd('fibonacciIterative()')
console.time('fibonacci()')
console.log(fibonacci(45))
console.timeEnd('fibonacci()')
// 1134903170
// fibonacciIterative(): 0.579ms
// 1134903170
// fibonacci(): 8.260s
测试表明迭代版本比递归版本要快很多。
但是迭代版本更容易理解，所需的代码也更少，此外，对于某些算法，迭代的解法可能不可用。
记忆化的优化技术
执行 fibonacci(45) 既然花费了 8 秒，时间花在哪里？
假如我们要计算 fibonacci(5)，调用情况如下：
fibonacci(3) 被调用 2 次，fibonacci(2) 被调用 3 次，fibonacci(1) 调用了 5 次。
我们可以将结果存下来，当需要再次计算它的时候，我们就无需重复计算，直接返回结果即可。重写 fibonacci() 如下：
const fibonacciMemoization = (function () {
const mem = [0, 1]
function fibonacci(val) {
// 在缓存中则直接返回
if (mem[val]) {
return mem[val]
}
if (val <= 1) {
return val
}
const result = fibonacci(val - 1) + fibonacci(val - 2)
// 存入缓存中
mem.push(result)
return result
}
return fibonacci
}())
测试：
let num = 45
console.time('fibonacci()')
console.log(fibonacci(num))
console.timeEnd('fibonacci()')
console.time('fibonacciIterative()')
console.log(fibonacciIterative(num))
console.timeEnd('fibonacciIterative()')
console.time('fibonacciMemoization()')
console.log(fibonacciMemoization(num))
console.timeEnd('fibonacciMemoization()')
// 1134903170
// fibonacci(): 10.590s
// 1134903170
// fibonacciIterative(): 0.513ms
// 1134903170
// fibonacciMemoization(): 0.506ms
虽然递归版本花费 10s，但是记忆化优化版本只花费 0.5ms，和迭代版本所花时间几乎相同。
其他章节请看：
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
