《学习JavaScript数据结构与算法》-- 6.递归(笔记)

爱学习的程序媛

发布于 2022-04-07 16:17:53

5830

文章被收录于专栏：学习/读书笔记学习/读书笔记

递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。递归通常涉及函数调用自身。

每个递归函数都需要有基线条件，即一个不再递归调用的条件（停止点），以防止无限递归。

6.1 计算一个数的阶乘

6.1.1 迭代阶乘

function factorialIterative(number) {
    if (number < 0) {
        return undefined;
    }
    let total = 1;
    for (let n = number; n > 1; n--) {
        total = total * n;
    }
    return total;
}

6.1.2 递归阶乘

function factorial(n) {
    if (n < 0) {
        return undefined;
    }
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

1）调用栈

在程序运行时，计算机会为应用程序分配一定的内存空间，应用程序则会自行分配所获得的内存空间，其中一部分被用于记录程序中正在调用的各个函数的运行情况，这就是函数的调用栈。

常规的函数调用总是会在调用栈最上层添加一个新的堆栈帧（stack frame，也称为“栈帧”或“帧”），这个过程被称作“入栈”或“压栈”（即把新的帧压在栈顶）。

当函数的调用层数非常多时，调用栈会消耗不少内存，甚至会撑爆内存空间（栈溢出，stack overflow），造成程序严重卡顿或意外崩溃。

2）ES6尾调用优化（tail call optimization）

尾调用优化不再创建新的栈帧，而是清除并重用当前栈帧，所以可以帮助函数保持更小的调用栈，减少内存的使用，避免栈溢出错误。

对于递归函数，如果没有尾调用优化，持续递归一段时间后，由于递归调用次数多，可能导致调用栈溢出，引发错误。进行优化后，调用栈中只会存在一个栈帧，避免栈溢出错误。

在进行编写递归函数时，利用尾调用优化的特性优化递归函数，将会提升程序的性能。

3）ES6尾调用优化需满足三个条件

⑴ 尾调用不访问当前栈帧的变量；

⑵ 在函数内部，尾调用是最后一条语句；

⑶ 尾调用的结果作为函数值返回。

4）尾调用优化递归阶乘

function factorial(n, p = 1) {
    if (n < 0) {
        return undefined;
    }
    if (n <= 1) {
        return 1 * p;
    }
    let res = n * p
    return factorial(n - 1, res);
}

6.2 斐波那契数列

斐波那契数列是一个由0、1、1、2、3、5、8、13、21、34等数组成的序列。

位置0的斐波那契数是0，位置1和2的斐波那契数是1，位置n（n > 2）的斐波那契数是位置（n - 1）的斐波那契数加上位置（n - 2）的斐波那契数。

6.2.1 迭代求斐波那契数

function fibonacciIterative(n) {
    if (n < 1) return 0;
    if (n <= 2) return 1;
    let fibNum1 = 0;
    let fibNum2 = 1;
    let fibN = n;
    for (let i = 2; i <= n; i++) {
        fibN = fibNum1 + fibNum2;
        fibNum1 = fibNum2;
        fibNum2 = fibN;
    }
    return fibN;
}

6.2.2 递归求斐波那契数

function fibonacci(n) {
    if (n < 1) return 0;
    if (n <= 2) return 1;
    return fibonacci(n - 2) + fibonacci(n - 1);
}

6.2.3 记忆化斐波那契数（记忆化是一种保存前一个结果的值的优化技术,类似于缓存）

function fibonacciMemoization() {
    const memo = [0, 1];
    const fibonacci = n => {
        if (memo[n] != null) return memo[n];
        return memo[n] = fibonacci(n - 2, memo) + fibonacci(n - 1, memo);
    }
    return fibonacci;
}

详细代码：

https://github.com/chenxiaohuan117/learning-javasrcipt-note/tree/main/%E3%80%8A%E5%AD%A6%E4%B9%A0JavaScript%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E3%80%8B(%E7%AC%AC3%E7%89%88)

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-10，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法