接着讲递归遍历

共 1982字,需浏览 4分钟

 ·

2021-02-08 14:23

递归遍历

递归的另一个重要应用是递归遍历。

想象一下,我们有一家公司。人员结构可以表示为一个对象:

let company = {
  sales: [{
    name'John',
    salary1000
  }, {
    name'Alice',
    salary1600
  }],

  development: {
    sites: [{
      name'Peter',
      salary2000
    }, {
      name'Alex',
      salary1800
    }],

    internals: [{
      name'Jack',
      salary1300
    }]
  }
};

换句话说,一个公司有部门。

一个部门可能有一系列的员工。例如,销售部有两名员工:John和Alice。

或者一个部门可以分为子部门,比如开发部门有两个分支:站点和内部。他们每个人都有自己的员工。

当一个子部门增长时,它也有可能划分为子部门(或团队)。

例如,未来的站点部门可能会被分为siteA和siteB两个团队。而且,它们可能会分裂得更多。这不在图上,只是在脑海里。

现在假设我们想要一个函数来得到所有工资的总和。我们怎么做呢?

迭代的方法并不容易,因为结构并不简单。第一个想法可能是在公司上创建一个for循环,在第一级部门上嵌套子循环。但是,我们需要更多嵌套的子循环来迭代第二级部门(如站点)的员工……然后在那些第三级部门中再出现一个子循环,将来会出现吗?如果我们在代码中放置3-4个嵌套的子循环来遍历单个对象,它就会变得相当丑陋。

让我们尝试递归。

正如我们所看到的,当函数得到一个要求和的部门时,有两种可能的情况:

它要么是一个拥有一组人员的“简单”部门——然后我们可以在一个简单的循环中对工资进行合计。

或者它是一个有N个子部门的对象——然后我们可以进行N次递归调用,以得到每个子部门的和并组合结果。

第一种情况是递归的基础,这种简单的情况,当我们得到一个数组。

当我们得到一个对象的第二种情况是递归步骤。一个复杂的任务被分割成小部门的子任务。他们可能会再次分裂,但迟早会在(1)处结束分裂。

从代码中读取算法可能更容易:

let company = { // the same object, compressed for brevity
  sales: [{name'John'salary1000}, {name'Alice'salary1600 }],
  development: {
    sites: [{name'Peter'salary2000}, {name'Alex'salary1800 }],
    internals: [{name'Jack'salary1300}]
  }
};

// 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返回它们的数组。


浏览 41
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报