数据结构与算法-递归

《学习JavaScript数据结构与算法(第3版)》

递归通常涉及函数调用自身。间接调用自身的函数也是递归函数。

每个递归函数都必须有基线条件，即一个不再递归调用的条件（停止点），以防止无限递归，出现栈溢出错误。

function recursiveFunction(someParam) {
    recursiveFunction(someParam);
}

计算一个数的阶乘

数n的阶乘，定义为n!，表示从1到n的整数的乘积。

迭代阶乘

可以从给定的number开始计算阶乘，并减少n，直到它的值为2，因为1的阶乘还是1，而且它已经被包含在total变量中了。零的阶乘也是1。负数的阶乘不会被计算。

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

递归阶乘

function factorial(n) {
    if (n < 0) {
        return undefined;
    }
    if (n === 1 || n === 0) { // 基线条件
        return 1;
    }
    return n * factorial(n - 1); // 递归调用
}

调用栈：每当一个函数被一个算法调用时，该函数会进入调用栈的顶部。当使用递归的时候，每个函数调用都会堆叠在调用栈的顶部，这是因为每个调用都可能依赖前一个调用的结果。

每个浏览器都有自己的调用栈大小限制。

尾调用优化 & 尾递归

尾调用是指某个函数的最后一步是调用另一个函数。

尾调用不一定出现在函数尾部，只要是最后一步操作即可。

尾调用之所以与其他调用不同，就在于它的特殊的调用位置。

// 情况一
function f(x){
    let y = g(x);
    return y;
}

// 情况二
function f(x){
    return g(x) + 1;
}

// 情况二才属于尾调用

函数调用会在内存形成一个”调用记录”，又称”调用帧”（call frame），保存调用位置和内部变量等信息。

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了，只要直接用内层函数的调用记录，取代外层函数的调用记录就可以了。

如果不是尾调用，就需要保存每一步函数调用的内部数据，但是如果是尾调用就只保存最后一步的调用数据。

尾调用优化（Tail call optimization）：即只保留内层函数的调用记录。如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存。

尾递归：如果尾调用自身，就称为尾递归。

递归非常耗费内存，因为需要同时保存成千上百个调用记录，但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生”栈溢出”错误。

使用尾递归优化上一部分的迭代阶层递归调用，空间复杂度从O(n)变为O(1)

// 尾递归
function factorial(n, total = 1) {
    if (n === 1) return total
    return factorial(n-1, n * total)
}

// 柯里化，将多参数的函数转换成单参数的形式
function currying(fn, n) {
    return function (m) {
        return fn.call(this, m, n);
    };
}

function tailFactorial(n, total) {
    if (n === 1) return total;
    return tailFactorial(n - 1, n * total);
}

尾调用优化发生时，函数的调用栈会改写，因此arguments（返回调用时函数的参数）和func.caller（返回调用当前函数的那个函数）两个变量就会失真。严格模式禁用这两个变量，所以尾调用模式仅在严格模式下生效。

斐波那契数列

是一个由0、1、1、2、3、5、8、13、21、34等数组成的序列。数2由1+1得到，数3由1+2得到，数5由2+3得到。

位置0的斐波那契数是零。

1和2的斐波那契数是1。

n（此处n > 2）的斐波那契数是（n -1）的斐波那契数加上（n -2）的斐波那契数。

迭代

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

递归

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

尾递归

尾递归：递归是从大到小n,n-1,n-2…1，尾递归是从小到大1,2…n-1,n

function fibonacci(n, a = 1, b = 1) {
    if (n <= 1) {
        return b
    }
    return fibonacci(n-1, b, a + b)
}

记忆化(动态规划)

记忆化是一种保存前一个结果的值的优化技术，类似于缓存。如果我们分析在计算fibonacci(5)时的调用，会发现fibonacci(3)被计算了两次，因此可以将它的结果存储下来，这样当需要再次计算它的时候，我们就已经有它的结果了。

function fibonacciMemoization(n) {
    if (n < 1) { return 0; }
    const memo = [0, 1]; // 用于缓存所有的计算结果
    const fibonacciMem = num => {
        if (memo[num] != null) { return memo[num]; } // 如果结果已经被计算了，就直接返回
        return (memo[num] = fibonacciMem(num - 1) + fibonacciMem(num - 2)); // 否则将计算结果并加入缓存
    };
    return fibonacciMem(n);
}

迭代与递归

有的时候迭代版本要比递归版本运行速度更快，但是递归版本要比迭代版本所需的代码量小，使用尾递归优化可能能够消除递归带来的多余消耗。

参考链接

尾调用优化 - 阮一峰