递归

什么是递归

定义：当一个函数解决一个任务时，在解决的过程中它可以调用很多其它函数。在部分情况下，函数会调用 自身。这就是所谓的 递归。

如何写出递归？

• 写出递归公式
• 找到临界条件

当一个函数调用自身时，称其为递归步骤。递归的基础是函数参数使任务简单到该函数不再需要进行下一步调用。

备注：上面这句话该如何用代码去理解

1.数字求和
//编写一个函数 sumTo(n) 计算 1 + 2 + ... + n 的和。
//使用递归，对 n > 1 执行 sumTo(n) = n + sumTo(n-1)。
function sumTo(n) {
  if (n == 1) return 1;
  return n + sumTo(n - 1);
}
alert( sumTo(100) );
2.计算阶乘
//n! = n * (n - 1) * (n - 2) * ...*1
//递归的基础是数值 1。我们也可以用 0 作为基础，不影响，除了会多一次递归步骤：
function factorial(n) {
  return n ? n * factorial(n - 1) : 1;
}
alert( factorial(5) ); // 120
// 清晰一点
function factorial(n) {
  if (n == 1) {
    return n;
  } else {
    return n * factorial(n - 1);
  }
}

应用

对数字求和到给定值

计算阶乘

斐波那契数列