递归

递归

概念

  • 方法自己调用自己
  • 有终止条件

初识

Q:获取1-100的累加总和
方法为sum(100) 100为累计的数值点
那么,总和就是

1
2
3
4
5
function sum (n) {
if (n === 1) return 1
return n + sum(n-1)
}
sum(100) // 5050

Q: 获取1-100能被5整除的元素的集合

1
2
3
4
5
6
7
function sum5 (n) {
console.log(n)
if (n <= 0) return 0
if (n % 5 === 0) return n + sum5(n - 5)
return sum5(n - 1)
}
sum5(100) // 1050

规律

不满足条件直接跳出递归
总是自身调用自身

1
2
3
4
5
sum(5) = 5 + sum(5 - 1)   // 15
= 5 + 4 + sum(4 - 1)
= 5 + 4 + 3 + sum(3 - 1)
= 5 + 4 + 3 + 2 + sum(2 - 1)
= 5 + 4 + 3 + 2 + 1 + sum(1 - 1)

其中 sum(0) = 0 结果为5 + 4 + 3 + 2 + 1 = 15

使用场景

  • 多层数据操作

尾递归

就拿刚刚的sum方法来说,在浏览器执行sum(100000)
会发现报错:Maximum call stack size exceeded
这会导致堆栈溢出
而解决方法就是 尾递归

1
2
3
4
function sum (n, total = 0) {
if (n === 0) return total
return sum(n - 1, n + total)
}

而之前的sum5方法也可以使用尾递归计算

1
2
3
4
5
function sum5 (n, total = 0) {
if (n === 0 ) return total
if (n % 5 !== 0) return sum5(n - 1, total)
return sum5(n - 5, n + total)
}

但是我也执行了一下发现好像都会堆栈溢出。。。