接着讲递归遍历
共 1982字，需浏览 4分钟
· 2021-02-08
递归遍历
递归的另一个重要应用是递归遍历。
想象一下，我们有一家公司。人员结构可以表示为一个对象:
let company = {
sales: [{
name: 'John',
salary: 1000
}, {
name: 'Alice',
salary: 1600
}],
development: {
sites: [{
name: 'Peter',
salary: 2000
}, {
name: 'Alex',
salary: 1800
}],
internals: [{
name: 'Jack',
salary: 1300
}]
}
};
换句话说，一个公司有部门。
一个部门可能有一系列的员工。例如，销售部有两名员工:John和Alice。
或者一个部门可以分为子部门，比如开发部门有两个分支:站点和内部。他们每个人都有自己的员工。
当一个子部门增长时，它也有可能划分为子部门(或团队)。
例如，未来的站点部门可能会被分为siteA和siteB两个团队。而且，它们可能会分裂得更多。这不在图上，只是在脑海里。
现在假设我们想要一个函数来得到所有工资的总和。我们怎么做呢?
迭代的方法并不容易，因为结构并不简单。第一个想法可能是在公司上创建一个for循环，在第一级部门上嵌套子循环。但是，我们需要更多嵌套的子循环来迭代第二级部门(如站点)的员工……然后在那些第三级部门中再出现一个子循环，将来会出现吗?如果我们在代码中放置3-4个嵌套的子循环来遍历单个对象，它就会变得相当丑陋。
让我们尝试递归。
正如我们所看到的，当函数得到一个要求和的部门时，有两种可能的情况:
它要么是一个拥有一组人员的“简单”部门——然后我们可以在一个简单的循环中对工资进行合计。
或者它是一个有N个子部门的对象——然后我们可以进行N次递归调用，以得到每个子部门的和并组合结果。
第一种情况是递归的基础，这种简单的情况，当我们得到一个数组。
当我们得到一个对象的第二种情况是递归步骤。一个复杂的任务被分割成小部门的子任务。他们可能会再次分裂，但迟早会在(1)处结束分裂。
从代码中读取算法可能更容易:
let company = { // the same object, compressed for brevity
sales: [{name: 'John', salary: 1000}, {name: 'Alice', salary: 1600 }],
development: {
sites: [{name: 'Peter', salary: 2000}, {name: 'Alex', salary: 1800 }],
internals: [{name: 'Jack', salary: 1300}]
}
};
// The function to do the job
function sumSalaries(department) {
if (Array.isArray(department)) { // case (1)
return department.reduce((prev, current) => prev + current.salary, 0); // sum the array
} else { // case (2)
let sum = 0;
for (let subdep of Object.values(department)) {
sum += sumSalaries(subdep); // recursively call for subdepartments, sum the results
}
return sum;
}
}
alert(sumSalaries(company)); // 7700
代码很短，容易理解(希望如此?)这就是递归的力量。它也适用于任何层次的子部门嵌套。
下面是调用的图表:
我们很容易看到这个原则:对于一个对象{…}子调用，而数组是递归树的“叶”，它们给出直接的结果。
注意，代码使用了我们之前介绍过的智能特性:
加勒比海盗的方法。reduce在Array方法中解释了获取数组和的方法。
循环(val of object .values(obj))以遍历对象值:object。values返回它们的数组。