递归

函数直接或间接调用自身

斐波拉契数列.js

//求斐波拉契数列第n位的值
//1  1  2  3  5  8  13  21  ...
//f(1): 1   f(2): 1
//f(3) = f(2) + f(1)    f(5) = f(4)+f(3)
//f(n) = f(n-1) + f(n-2)

//斐波拉契数列的第n位
function f(n) {
    if (n === 1 || n === 2) {
        return 1;
    }
    return f(n - 1) + f(n - 2);
}

console.log(f(5));

阶乘.js

 //5! = 5*4*3*2*1
//f(n)
//f(1) = 1
//f(2) = 2*f(1)
//f(3) = 3*f(2)
//n的阶乘 n!
function fn(n, total) {
    if (n === 1) {
        return 1;
    }
    return n * fn(n-1);
}

console.log(f(5));

避免无限递归，无限递归会导致执行栈溢出。

对比死循环

• 死循环不会报错，也不会导致栈溢出
• 无限递归会导致栈溢出

执行栈

任何代码的执行都必须有一个执行环境，执行环境为代码的执行提供支持

执行环境是放到执行栈中的。

每个函数的调用，都需要创建一个函数的执行环境，函数调用结束，执行环境销毁。

执行栈有相对固定的大小，如果执行环境太多，执行栈无法容纳，会报错

想象一下执行栈为一个水桶,全局执行栈会在最底,然后每遇到一个函数的执行都必须开启一个新的执行栈。基于这一点，才会出现递归的栈溢出错误。 而死循环只有开启了一个执行栈,由于死循环函数一直没有执行完，所以该执行栈一直没销毁，但是不会产生执行栈的溢出。

尾递归

如果一个函数最后一条语句是调用函数，并且调用函数不是表达式的一部分，则该语句称为尾调用，如果尾调用是调用自身函数，则称为尾递归。

某些语言或执行环境会对尾调用进行优化，它们会理解销毁当前函数，避免执行栈空间被占用。

在浏览器执行环境中，尾调用没有优化。但在nodejs环境中有优化。

针对尾递归的优化就是，执行栈不会再等待函数执行完再销毁，而是直接立即销毁，因为没有依赖任何表达式，直接返回的就是函数的结果

//5! = 5*4*3*2*1
//f(n)
//f(1) = 1
//f(2) = 2*f(1)
//f(3) = 3*f(2)
//n的阶乘 n!
function fhelper(n, total) {
    if (n === 1) {
        return total;
    }
    return fhelper(n - 1, n * total);//尾递归-nodejs中会有优化
}

function f(n) {
    return fhelper(n, 1);
}

console.log(f(5));

技巧

• 先找出递归的边界
• 找出递归关系：思考缩小一层的逻辑，然后自己调用自己
• 递归核心思维 ——"自顶向下拆解，自底向上返回"。

案例

数组累加和.js

let arr = [1, 23, 3, 4, 5];

const sum = (arr) => {
    // 1. 找出边界
    if (arr.length == 0) {
        return 0;
    }
    // 2. 找出递归关系(缩小一级思考情况)
    return arr[0] + sum(arr.slice(1));
}

数组求最大值.js

let arr = [1, 23, 3, 4, 5];

const max = (arr) => {
    // 1. 找出边界
    if (arr.length == 1) {
        return arr[0];
    }
    // 2. 找出递归关系，拆解问题
    let maxNum = max(arr.slice(1));

    return arr[0] > maxNum ? arr[0] : maxNum;
}

汉诺塔.js

function hannuo(no1, no2, no3, n) {
    if (n === 1) {
        console.log(`${no1}->${no3}`);
    } else {
        hannuo(no1, no3, no2, n - 1);
        console.log(`${no1}->${no3}`);
        hannuo(no2, no1, no3, n - 1);
    }
}

hannuo('A', 'B', 'C', 5);