递归函数

什么是递归？

递归函数就是在函数内部，直接或者间接调用自己

function func(let n) {
    if (n === 1) {
        return n;
    }
    // 自己调用自己
    return func(n - 1) * n;
}

1. 直接调用

function func(let n) {
    if (n === 1) {
        return n;
    }
    // 自己调用自己
    return func(n - 1) * n;
}

2. 间接调用

function fun1(a) {
    let b = fun2(a + 1);
}

function fun2(s) {
    let c = fun1(s - 1);
}

如何设计递归函数？

1. 递归函数，必须要有一个结束条件
2. 在递归中，一个问题可以被分解为多个子问题，子问题是父问题的实例，可以用相同的方法解决
3. 在递归中，每次递归都要向结束条件靠拢
4. 递归函数，每次递归都需要有一个返回值，并且用递归的值来计算

递归函数有什么缺点？

1. 空间效率低，每次函数进行递归，都会创建一个新的函数实例
2. 可能导致栈溢出，递归次数越多，内存消耗越大
3. 递归可能会重复计算，子问题基本相同

如何优化递归函数？

• 使用尾递归
• 循环代替递归
• 使用动态规划/记忆化技术