简介
递归是编程中一个很强大的概念，它指的是函数调用自身。
一开始可能有点难理解，但只要掌握了基本原理，它就会成为解决复杂问题的有力工具。
在本教程中，我们会用简单易懂的例子来探索 JavaScript 中的递归。
什么是递归？
递归是指函数直接或间接地调用自身。
它和循环有些类似，但会把问题拆解成更小、更容易处理的子问题。
例 1：倒计时
我们先从一个简单的例子开始：一个倒计时函数。
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
在这个例子中：
-
基准情况：当
num小于或等于 0 时，函数会打印“Blastoff!”，并停止调用自身。
-
递归情况：函数打印当前的
num，然后用num - 1调用自身。
例 2：阶乘
接下来，我们来看一个递归的经典例子：计算一个数字的阶乘。
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
在这个例子中：
-
基准情况：当
n为 0 或 1 时，函数返回 1。
-
递归情况：函数将
n乘以n - 1的阶乘。
核心概念
基准情况
每个递归函数都必须至少有一个基准情况，也就是函数停止调用自身的条件。
如果没有基准情况，递归就会一直进行下去，最终导致栈溢出。
递归情况
递归情况定义了函数如何用更小或更简单的问题来调用自身。
递归的优缺点
优点：
- 对某些问题来说是很优雅的解法。
- 与数学归纳法的思路相似。
缺点：
- 可能比迭代解法效率更低。
- 递归过深时可能导致栈溢出。
总结
递归是一种很有价值的技术，它把复杂的问题拆成更小、更容易处理的子问题，从而化繁为简。
理解基准情况和递归情况，是在 JavaScript 中写出有效递归解法的关键。
了解更多：
说明
你经营着一家披萨店，提供三种披萨：
- Margherita：7 美元
- Caprese：9 美元
- Formaggio：10 美元
如果顾客愿意，可以添加任意数量的额外选项：“ExtraSauce”加 1 美元，“ExtraToppings”加 2 美元。
你的任务是编写代码，帮助顾客算出自己要付多少钱。
计算一个披萨的价格
第一个实参是披萨的名称，后面可以跟任意数量的额外选项，请以美元为单位计算这个披萨的价格。
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
计算一笔订单的总价
你的函数会接收一个由 PizzaOrder 组成的数组，并返回这笔订单的总价，以美元为单位。每个 PizzaOrder 都有一个pizza属性，也就是披萨的名称，还有一个extras属性，也就是额外选项的数组。
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
你会发现，这没法用递归来实现，因为其中一个包含大量订单的测试会抛出Maximum call stack size exceeded。别担心，这是有意为之，试着用命令式循环来实现这个函数吧！你有很多选择，比如使用reduce或for循环，但不限于此。
当 JavaScript 翻译运行 JavaScript 代码时，它会用一个叫“栈”的数据结构来记录自己进入了（也就是开始调用）哪些函数。当函数返回（结束）时，它就会从栈中移除。
不过，这个栈的大小是有限的。最常见的错误就是写了一个永远不会结束的递归函数。每次调用都会压入栈中，但在它返回之前，又有另一次调用被压入栈中。
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
这个错误的栈跟踪会反复显示同一行，这很合理，因为这个函数调用了它自己。虽然大多数情况下这并没有什么实际用途，但你可以弄清楚这个栈最高能有多高。
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
对于由同步递归函数引起的调用栈错误，只有两种可行的解决方案：
- 确保函数在达到栈上限之前返回，通常需要添加或修正基本情况。
- 把递归函数改写成命令式循环。这样会直接执行循环体，不需要进入函数，因此不会增加栈的深度。
学习练习
