递归函数

概念

如果一个函数在内部调用这个函数自身，这个函数就是递归函数。

递归在数据结构和算法中经常用到，可以将很多复杂的数据模型拆解为简单问题进行求解。一定要掌握。

递归的要素

• 递归模式：把大问题拆解为小问题进行分析。也称为递归体。
• 边界条件：需要确定递归到何时结束。也称为递归出口。

代码演示：计算阶乘

提问：求一个正整数的阶乘。

普通写法：

// 函数：计算一个正整数的阶乘
function factorial(n) {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

console.log(factorial(5)); // 120

现在，我们学习了递归函数之后，会有更简洁的写法。

递归写法：

// 递归函数：计算一个正整数的阶乘
function factorial(n) {
  // 递归出口：如果计算1的阶乘，就不用递归了
  if (n == 1) return 1;

  // 开始递归：如果当前这个 n 不是1，就返回 n * (n-1)!
  return n * factorial(n - 1);
}
console.log(factorial(5)); // 120

递归函数的案例

寻找所有的喇叭花数

题目：喇叭花数是一个三位数，其每一位数字的阶乘之和恰好等于它本身，即abc＝a! + b! + c!，其中abc表示一个三位数。请找出所有的喇叭花数。

思路：将计算某个数字的阶乘封装成函数。

代码实现：

// 递归函数：计算一个数的阶乘
function factorial(n) {
  // 递归出口：如果计算1的阶乘，就不用递归了
  if (n == 1) return 1;

  // 开始递归：如果当前这个 n 不是1，就返回 n * (n-1)!
  return n * factorial(n - 1);
}

// 穷举法，从100到999遍历，寻找喇叭花数
for (let i = 100; i <= 999; i++) {
  // 将数字i转为字符串
  const i_str = i.toString();
  // abc分别表示百位、十位、个位
  const a = Number(i_str[0]);
  const b = Number(i_str[1]);
  const c = Number(i_str[2]);

  // 根据喇叭花数的条件进行判断
  if (factorial(a) + factorial(b) + factorial(c) == i) {
    console.log(i);
  }
}

打印结果：

145

斐波那契数列

斐波那契数列是这样一个数列：1、1、2、3、5、8、13、21、34......最早是由意大利数学家斐波那契开始研究的。它的规律是：下标为0和1的项，值为1；从下标为2的项开始，每一项等于前面两项之和。

提问：请找出斐波那契数列的前10项。

代码实现：

// 递归函数：返回斐波那契数列中下标为n的那一项的值
function fib(n) {
  // 下标为0和1的项，值为1
  if (n == 0 || n == 1) return 1;
  // 从下标为2的项开始，每一项等于前面两项之和
  return fib(n - 1) + fib(n - 2);
}

// 循环语句：打印斐波那契数列的前10项
for (let i = 0; i < 15; i++) {
  console.log(fib(i));
}

小结

关于递归的案例，今后我们还会学习更多的应用场景。比如深拷贝就会用到递归。