递归

在函数执行过程中调用其自身的循环结构，同时必须定义结束条件。 :::info 循环是从开始到结束不中断的迭代。递归会在执行过程中跳转到开头重新执行。 :::

使用递归结构完成迭代功能，一定要区分需要迭代的代码，而不需要迭代的部分代码一定要放到递归函数外面。

image.png

  1. function foo(n) {
  2.     console.log(`level: ${n}\n`);        //输出语句1
  3.     if (n < 4) {
  4.         foo(n + 1);                                    //递归调用语句
  5.     }
  6.     console.log(`level: ${n}\n`);        //输出语句2
  7. }
  8. foo(1);
  10. //output:
  11. level: 1
  12.     level: 2
  13.         level: 3
  14.             level: 4
  15.             level: 4
  16.         level: 3
  17.     level: 2
  18. level: 1

尾递归

在函数执行的最后一个步骤，调用其自身的过程。

function foo(n) {    
    if(n > 0){
    return n + foo(n - 1);    //不是尾递归，因为返回的函数还执行加法运算。
    } else {
    return 0;
    }    
}
console.log(foo(10));

:::info 尾递归直接返回函数，不能再执行其他操作。 :::

尾递归优化

js引擎对于尾递归优化，可以重用堆栈。

function factorial(num) {
  let sum = 1;    //该语句只需要执行一次，不能放到递归函数里面。
  return factorialRecursion(num);

  function factorialRecursion(num) {
    if (num <= 1) {
      return sum
    }
    sum *= num
    return factorialRecursion(num - 1);
  }
}