递归函数

递归函数

什么是递归？

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

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. 递归可能会重复计算，子问题基本相同

如何优化递归函数？

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