JavaScript 基础
Document
运算符
深入数据和类型
函数进阶
原型、继承
类
浏览器存储
Web API
事件
错误处理
异步编程
网络请求
模块
练习
实例
工具与规范
软件架构模式
设计模式
递归
递归是一种编程技巧,当一个函数在运行过程中调用自身,便被称为递归。
当我们计算一个数的阶乘时,第一反应是用循环,那么写法如下:
$$jsdemo$$
$$edit$$
function factorial(n) {
let result = 1
for (let i = 1; i <= n; i++) {
result *= i
}
return result
}
alert(factorial(5)) // 120
如果我们改用递归的思路,那么写法如下:
$$jsdemo$$
$$edit$$
function factorial(n) {
// 阶乘
if (n === 1) {
return 1
}
return n * factorial(n - 1)
}
alert(factorial(5)) // 120
$$tip
递归函数有一个特征,至少有两个 return
分支,一个是非递归调用的返回值(通常称为出口),另一个是递归调用的返回值。
$$
递归遍历
以下例子中,使用递归对一个多维数组进行了遍历,对所有的数字求和。
$$jsdemo$$
$$edit$$
const numbers = [
5,
100,
31,
[66, 77, 20],
55,
[4, 5, 6, [9, [11, 22, 33], 8, 7]],
]
function sum(x) {
if (Array.isArray(x)) {
// 数组,递归求和
let total = 0
x.forEach(function (item) {
total += sum(item)
})
return total
} else {
// 数字,直接返回
return x
}
}
alert(sum(numbers)) // 459
练习
- 用递归实现一个函数,接收
n
、x
两个正整数,随机返回小于n
且能被x
整除的正整数。
function randInt(n, x) {
// 补充完成
}
// 小于 100 的随机数,且能被 3 整除。
alert(randInt(100, 3)) // 27
alert(randInt(100, 3)) // 75
alert(randInt(100, 3)) // 60
$$answer
$$jsdemo$$
$$edit$$
function randInt(n, x) {
console.assert(n > x, "n 必须大于 x")
const result = Math.floor(Math.random() * n)
if (result != 0 && result % x === 0) {
return result
}
return randInt(n, x)
}
// 小于 100 的随机数,且能被 3 整除。
alert(randInt(100, 3)) // 27
alert(randInt(100, 3)) // 75
alert(randInt(100, 3)) // 60
$$
- 存在如下的公司员工数据,用递归求出总的薪水( 所有
salary
的和)。
const company = {
sale: [
{
name: "小青",
salary: 750,
},
{
name: "小紫",
salary: 950,
},
],
development: {
app: {
android: [
{
name: "小明",
salary: 1000,
},
],
ios: [
{
name: "小红",
salary: 800,
},
],
},
web: [
{
name: "小蓝",
salary: 1200,
},
{
name: "小绿",
salary: 900,
},
],
},
}
function sumSalary(department) {
// 补充完成
}
// 总薪水
alert(sumSalary(company)) // 5600
$$answer
$$jsdemo$$
$$edit$$
const company = {
sale: [
{
name: "小青",
salary: 750,
},
{
name: "小紫",
salary: 950,
},
],
development: {
app: {
android: [
{
name: "小明",
salary: 1000,
},
],
ios: [
{
name: "小红",
salary: 800,
},
],
},
web: [
{
name: "小蓝",
salary: 1200,
},
{
name: "小绿",
salary: 900,
},
],
},
}
function sumSalary(department) {
if (Array.isArray(department)) {
return department.reduce(
(prev, current) => prev + current.salary,
0
) // 数组薪资的和
} else {
let sum = 0
for (let item of Object.values(department)) {
sum += sumSalary(item)
}
return sum
}
}
// 总薪水
alert(sumSalary(company)) // 5600
$$