• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 2分钟前 1次浏览

递归

递归的概念

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

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

// 直接调用自身
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)。


程序员灯塔
转载请注明原文链接:前端学习 数据结构与算法 快速入门 系列 —— 递归
喜欢 (0)