其他章节请看:

前端学习 数据结构与算法 快速入门 系列

递归

递归的概念

递归是一种解决问题的方法,它从解决问题的各个小部分开始,直到解决最初的大问题。

递归通常涉及调用函数本身,直接调用自身,亦或者间接调用自身,都是递归函数。就像这样:

// 直接调用自身
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),调用情况如下:

graph TD a["fibonacci(5)"] --> b["fibonacci(4)"] a["fibonacci(5)"] --> c["fibonacci(3)"] b["fibonacci(4)"] --> d["fibonacci(3)"] b["fibonacci(4)"] --> e["fibonacci(2)"] c["fibonacci(3)"] --> f["fibonacci(2)"] c["fibonacci(3)"] --> g["fibonacci(1)"] d["fibonacci(3)"] --> h["fibonacci(2)"] d["fibonacci(3)"] --> i["fibonacci(1)"]

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,和迭代版本所花时间几乎相同。

其他章节请看:

前端学习 数据结构与算法 快速入门 系列

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/pengjiali/p/15585433.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!