专栏首页京程一灯JS编程: 递归

JS编程: 递归

想成为一个更好的开发者,那么理解数据结构、算法和基本编程思想是必须的。现在大多数问题都被现代工具和各种库解决了,但是对这些领域有一个更深的了解,将会大大拓宽你软件开发的视野。

就我自己而言,掌握这些概念是相当困难的,因为在我每天的工作里,几乎都不用这些。我正在写的这一系列文章就是为了提升我和那些跟我一样的人对这些方面的理解。

什么是递归

递归是主要的编程思想之一。毫无疑问,你已经在一些算法书籍和文章里,以及计算斐波纳契数列或者相似内容的例子里,看到了一些可怕的词汇。但作为一个网页开发人员,在你的日常编码工作或者实现排序算法时,可能并没有用到斐波纳契数列,至少我没有。

当我第一次开始阅读关于递归时,在理解哪里能被正确的使用时遇到了问题。我知道这个方法的好处以及在某些特定算法里的用途,但是很难找到更应该使用递归而不是迭代的场景。

在继续之前——本文希望你对递归和JavaScript有一个基本的了解。所以,让我们从一个我觉得容易理解的定义开始:

递归就是一个函数调用自身,直到达到某个特定状态。

让我们把它分为两部分,然后分别讨论。一个调用自身的函数意思是在函数体内,我们将调用同一个函数——初始化(inception),对吗?你第一次看见一个递归函数的时候,可能会打破你对函数执行的理解,但它绝对是正常的。

当我们使用递归,它会一直持续到到达某一特定状态为止。在某些情况下,我们调用函数必须是固定次数。但在其它情况下,它会持续运行,直到一个条件检查告诉它停下。这两种情况,我们都必须有一个明确的停止条件,以防止递归一直执行。

应用递归

定义和解释并不能让我们实现什么,所以让我们从一个实际的例子开始。我们将使用递归来说明怎样把一个分类列表排序成树状机构。这里是我们从服务端获取到的分类,它们包含了自己的名字和父类:

const categories = [
 { name: 'tech', parent: null },
 { name: 'hot_right_now', parent: 'tech' },
 { name: 'upcomming_releases', parent: 'tech' },
 { name: 'gadgets', parent: 'tech' },
 { name: 'news', parent: null },
 { name: 'social', parent: 'startups' },
 { name: 'europe', parent: 'news' },
 { name: 'asia', parent: 'news' },
 { name: 'events', parent: 'news' },
 { name: 'startups', parent: null },
 { name: 'funding', parent: 'startups' },
 { name: 'unicorns', parent: 'startups' },
 { name: 'venture_capital', parent: 'funding' },
 { name: 'crowdfunding', parent: 'funding' },
 { name: 'usa', parent: 'news' }
 ]

作为一个JavaScript开发人员,你的任务是把这些类排列为一个树状结构,以便展现在页面的某些地方。首先你能想到的是使用一些循环嵌套,然而这并不是一个优雅的方法。它暂时是可以正常工作的,但是这取决于列表结构以后都不变。如果某个时刻子节点删除或者增加,你将不得不修改你的代码。

这是一个说明什么时候使用递归比普通的迭代方法更好的完美示例。我们会从创建一个函数开始,它包含两个参数——一个数组和一个我们正在查询的类的父类。请记住,我们不仅仅是从全局接收类,因为我们将会递归地传入这些类。

const arrangeCategories = (category, parent) => {
  let result = {}
  // function body here
  return result
}

递归主体

接下来,我们需要正真的实现递归。我们的目标是得到一个不需要依赖嵌套层级的算法。这里是一个我们将要使用的完整函数:

const arrangeCategories = (categories, parent = null) => {
   let result = {}
   categories
     .filter(category => category.parent === parent)
     .forEach(category => {
       result[category.name] = arrangeCategories(categories, category.name)
     })
   return result
 }

让我们看看这都发生了什么。

  1. 在第4行,我们过滤类别,只得到正确的父项(在第一次调用时为空)
  2. 在我们拿到所需的类别后,遍历每一个我们作为结果对象的键所添加的类,并且递归调用,找到它的所有子类。
  3. 重复第一步

结果

在使用递归函数后,我们得到以下结果:

{
   "tech": {
     "hot_right_now": {},
     "upcomming_releases": {},
     "gadgets": {}
   },
   "news": {
     "europe": {},
     "asia": {},
     "events": {},
     "usa": {}
   },
   "startups": {
     "social": {},
     "funding": {
       "venture_capital": {},
       "crowdfunding": {}
     },
     "unicorns": {}
   }
 }

所有类别都经过排序,创建出一个更恰当的层级结构,以便更容易循环和展示。递归绝对是一个宽泛的话题,用它来解决问题比简单地列出未排序的分类要难的多,但这是一个不错的开始。

本文分享自微信公众号 - 京程一灯(jingchengyideng)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-08-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 聊聊flink的Execution Plan Visualization

    本文主要研究一下flink的Execution Plan Visualization

    codecraft
  • 第十八节 netty源码分析之 pipleline和handler以及pipeline的数据流向02

    下面是AbstractNioChannel的fulfillConnectPromise具体如下,

    用户1418372
  • React.js 实战 - 组件 & Props

    组件可以将UI切分成一些独立的、可复用的部件,这样你就只需专注于构建每一个单独的部件.

    JavaEdge
  • 一日一技:如何从Elasticsearch读取极大量的数据

    在使用Elasticsearch时,如果要返回少量的数据,我们可以在DSL语句中指定size这个参数来设定返回多少条数据:

    青南
  • 认识Set和Map数据结构

    tips : 由于 Set 结构没有键名,只有键值(或者说键名和键值是同一个值),所以keys方法和values方法的行为完全一致,而entries方法返回的...

    JianLiang
  • vue-cli3项目创建-配置-发布

    (2) 修改user module -- src/store/module/user.js

    RtyXmd
  • 基于django的视频点播网站开发-step9-后台视频管理功能

    从本讲开始,我们开始视频管理功能的开发,视频管理包括视频上传、视频列表、视频编辑、视频删除。另外还有视频分类的功能,会一同讲解。这一讲非常重要,因为你将学习到一...

    山东程序员
  • 快速入门Vue

    刚进公司做的第一个项目,刚好前端人手不足,需要我们后端同时兼顾前后端的工作,采用的iview UI框架,基于vue.js。

    KEN DO EVERTHING
  • 用beego vue.js element axios 写flow办公流程——系列五

    自己的认识:一定要用独立的前端,即vue.js前端项目必须是独立的,独立的服务,不要放beego里的view里作为tpl页面。虽然,放beego view里的t...

    hotqin888
  • RxJS 5 到 6迁移指导

    原文: https://rxjs-dev.firebaseapp.com/guide/v6/migration 转载地址: https://segment...

    mafeifan

扫码关注云+社区

领取腾讯云代金券