关于递归

递归

概念

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

初识

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)
}
但是我也执行了一下发现好像都会堆栈溢出。。。
下一篇 : 对象的继承方式