递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。

下面能够调用自身的函数，就是递归函数。每个函数都必须有一个基线条件，即一个不再递归调用的条件

1
2
3
4
5
6
7
function understandRecursion(someParam) {
    const recursionAnswer = confirm('xxx')
    if (recursionAnswer === true) {
        return true
    }
    understandRecursion(someParam)
}

计算一个数的阶乘

阶乘:数n的阶乘，定义为n!，表示从1到n的整数乘积。
5的阶乘表示为5!,5x4x3x2x1 = 120

for循环版本

1
2
3
4
5
6
7
8
9
function factorialIterative(number) {
   if (number < 0) return undefined
   let total = 1
   for (let i = number; number > 0; number--) {
    total = total*number
   }
   return total
 }
 console.log(factorialIterative(5)) // 120

递归版本

1
2
3
4
5
6
7
8
9
10
function factorial(n) {
   console.trace() // 跟踪函数的执行栈
   // 可以想象为当n=1时候，依次将之前的每一个值相乘
   if (n === 1 || n === 0) {
    return 1
   }
   return n * factorial(n-1)
 }
 console.log(factorial(5))

递归函数的调用栈

函数执行时候，按照函数调用顺序依次加入执行栈，最后等n===1时候开始依次弹出调用栈
image
image

ES6递归中的尾调用优化和尾递归

ES6尾调用优化只有在严格模式中开启，默认正常模式无效
尾调用优化-阮一峰

  • 尾调用:就是指某个函数的最后一步是调用另一个函数。
  • 尾递归:函数调用自身，称为递归。如果尾调用自身，就称为尾递归，递归非常耗费内存，可以使用尾递归来优化

斐波那契数列

1
2
3
4
5
6
function fibonacci(n){
    if (n < 1) return 0;
    if (n <= 2) return 1;
    return fibonacc(n-1)+fibonacc(n-2)
}

迭代和递归的效率

迭代循环版本比递归快很多，递归更慢，但是递归版本代码量更少