如何优雅的使用javascript递归画一棵结构树

徐小夕 等级 490 0 0

如何优雅的使用javascript递归画一棵结构树

递归和尾递归

简单的说,递归就是函数自己调用自己,它做为一种算法在程序设计语言中广泛应用。其核心思想是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。一般来说,递归需要有边界条件、递归前进阶段和递归返回阶段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

但是作为一个合格的程序员,我们也因该知道,递归算法相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储,递归次数过多容易造成栈溢出等。

这个时候,我们就需要用到尾递归,即一个函数中所有递归形式的调用都出现在函数的末尾,对于尾递归来说,由于只存在一个调用记录,所以永远不会发生"栈溢出"错误。

举个例子,我们来实现一下阶乘,如果用普通的递归,实现将是这样的:

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

最多需要保存n个调用栈,复杂度 O(n),如果我们使用尾递归:

function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

此时只需要保存一个调用栈,复杂度 O(1) 。通过这个案例,你是否已经慢慢理解其精髓了呢?接下来我将介绍几个常用的递归应用的案例,并在其后实现本文标题剖出的树的实现。

递归的常用应用案例

1. 数组求和

对于已知数组arr,求arr各项之和。

function sumArray(arr, total) {
    if(arr.length === 1) {
        return total
    }
    return sum(arr, total + arr.pop())
}

let arr = [1,2,3,4];
sumArray(arr, arr[1]) // 10

该方法给函数传递一个数组参数和初始值,也就是数组的第一项,通过迭代来实现数组求和。

2. 斐波那且数列

斐波那契数列(Fibonacci sequence),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(1)=1,F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)在现代物理、准晶体结构、化学等领域,斐波纳契数列都有直接的应用。接下来我们用js实现一个求第n个斐波那契数的方法:

// 斐波那契数列
function factorial1 (n) {
    if(n <= 2){
        return 1
    }
    return factorial1(n-1) + factorial1(n-2)
}

// 尾递归优化后
function factorial2 (n, start = 1, total = 1) {
    if(n <= 2){
        return total
    }
    return factorial2 (n -1, total, total + start)
}

由尾递归优化后的函数可以知道,每一次调用函数自身,都会将更新后的初始值和最终的结果传递进去,通过回溯来求得最终的结果。

3. 阶乘

阶乘在上文以提到过,如想回顾,请向上翻阅。

4. 省市级联多级联动

省市级联多级联动的方法本质是生成结构化的数据结构,在element或antd中都有对应的实现,这里就不做过多介绍了。

5. 深拷贝

深拷贝的例子大家也已经司空见惯了,这里只给出一个简单的实现思路:

 function clone(target) {
    if (typeof target === 'object') {
        let cloneTarget = Array.isArray(target) ? [] : {};
        for (const key in target) {
            cloneTarget[key] = clone(target[key]);
        }
        return cloneTarget;
    } else {
        return target;
    }
};

6. 爬梯问题

一共有n个台阶,每次只能走一个或两个台阶,问要走完这个台阶,一共有多少种走法。

n =1; result = 1  --> 1
n =2; result = 2  --> 11 2
n =3; result = 3  --> 111 12 21
...
如果第一步走1个台阶,由以上规律可以发现剩下的台阶有n-1种走法;
如果第一步走2个台阶,由以上规律可以发现剩下的台阶有n-2种走法;
则一共有fn(n-1) + fn(n-2) 种走法
function steps(n) {
    if(n <= 1) {
        return 1
    }
    return steps(n-1) + steps(n-2)
}

7. 对象数据格式化

这道题是本人曾经面试阿里的一道笔试题,问题是如果服务器返回了嵌套的对象,对象键名大小写不确定,如果统一让键名小写。

let obj = {
    a: '1',
    b: {
        c: '2',
        D: {
            E: '3'
        }
    }
}
转化为如下:
let obj = {
    a: '1',
    b: {
        c: '2',
        d: {
            e: '3'
        }
    }
}

// 代码实现
function keysLower(obj) {
    let reg = new RegExp("([A-Z]+)", "g");
    for (let key in obj) {
        if (obj.hasOwnProperty(key)) {
            let temp = obj[key];
            if (reg.test(key.toString())) {
                // 将修改后的属性名重新赋值给temp,并在对象obj内添加一个转换后的属性
                temp = obj[key.replace(reg, function (result) {
                    return result.toLowerCase()
                })] = obj[key];
                // 将之前大写的键属性删除
                delete obj[key];
            }
            // 如果属性是对象或者数组,重新执行函数
            if (typeof temp === 'object' || Object.prototype.toString.call(temp) === '[object Array]') {
                keysLower(temp);
            }
        }
    }
    return obj;
};

具体过程和思路在代码中已经写出了注释,感兴趣可以自己研究一下。

8. 遍历目录/删除目录

我们这里使用node来实现删除一个目录,用现有的node API确实有删除目录的功能,但是目录下如果有文件或者子目录,fs.rmdir && fs.rmdirSync 是不能将其删除的,所以要先删除目录下的文件,最后再删除文件夹。

function deleteFolder(path) {
    var files = [];
    if(fs.existsSync(path)) { // 如果目录存在
        files = fs.readdirSync(path);
        files.forEach(function(file,index){
            var curPath = path + "/" + file;
            if(fs.statSync(curPath).isDirectory()) { // 如果是目录,则递归
                deleteFolder(curPath);
            } else { // 删除文件
                fs.unlinkSync(curPath);
            }
        });
        fs.rmdirSync(path);
    }
}

9. 绘制分形图形

通过递归,我们可以在图形学上有更大的自由度,但是请记住,并不是最好的选择。

如何优雅的使用javascript递归画一棵结构树

如何优雅的使用javascript递归画一棵结构树 我们可以借助一些工具和递归的思想,实现如上的分形图案。

10. 扁平化数组Flat

数组拍平实际上就是把一个嵌套的数组,展开成一个数组,如下案例:

let a = [1,2,3, [1,2,3, [1,2,3]]]
// 变成
let a = [1,2,3,1,2,3,1,2,3]
// 具体实现
function flat(arr = [], result = []) {
    arr.forEach(v => {
        if(Array.isArray(v)) {
            result = result.concat(flat(v, []))
        }else {
            result.push(v)
        }
    })
    return result
}

flat(a)

当然这只是笔者实现的一种方式,更多实现方式等着你去探索。

用递归画一棵自定义风格的结构树

通过上面的介绍,我想大家对递归及其应用已经有一个基本的概念,接下来我将一步步的带大家用递归画一棵结构树。 效果图:

如何优雅的使用javascript递归画一棵结构树

如何优雅的使用javascript递归画一棵结构树 该图形是根据目录结构生成的目录树图,在很多应用场景中被广泛使用,接下来我们就来看看他的实现过程吧:

const fs = require('fs')
const path = require('path')
// 遍历目录/生成目录树
function treeFolder(path, flag = '|_') {
    var files = [];

    if(fs.existsSync(path)) {
        files = fs.readdirSync(path);
        files.forEach(function(file,index){
            var curPath = path + "/" + file;
            if(fs.statSync(curPath).isDirectory()) { // recurse
                // obj[file] = treeFolder(curPath, {});
                console.log(flag, file)
                treeFolder(curPath, '   ' + flag)
            } else {
                // obj['--'] = file
                console.log(flag, file)
            }
        })
        // return obj
    }
}

treeFolder(path.resolve(__dirname, './test'))

test为我们建的测试目录,如下:

如何优雅的使用javascript递归画一棵结构树 我们通过短短10几行代码就实现了一个生成结构树的小应用,是不是感觉递归有点意思呢?在这个函数中,第一个参数是目录的绝对路径,第二个是标示符,标示符决定我们生成的树枝的样式,我们可以自定义不同的样式。

欢迎大家相互学习交流,一起探索前端的边界。

更多推荐

收藏
评论区

相关推荐

4.2 手写Java PriorityQueue 核心源码
上一节介绍了PriorityQueue的原理,先来简单的回顾一下 PriorityQueue 的原理 以最大堆为例来介绍 1. PriorityQueue是用一棵完全二叉树实现的。 2. 不但是棵完全二叉树,而且树中的每个根节点都比它的左右两个孩子节点元素大 3. PriorityQueue底层是用数组来保存这棵完全二叉树的。 如下图,是一棵最大堆。
教你用200行代码写一个爱豆拼拼乐H5小游戏(附源码)
前言 本文将带大家一步步实现一个H5拼图小游戏,考虑到H5游戏的轻量级和代码体积,我没有使用react或vue这些框架,而采用我自己写的dom库和原生javascript来实现业务功能,具体库代码可见我的文章如何用不到200行代码写一款属于自己的js类库(https://juejin.im/post/6844903880707293198),构建工具我采
What the f*ck JavaScript?
What the fck JavaScript? 一个有趣和棘手的 JavaScript 示例列表。 JavaScript 是一种很好的语言。
JavaScript 中的二叉树以及二叉搜索树的实现及应用
接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树,有树干,树枝,在程序中树是一种数据结构,对于存储需要快速查找的数据非有用,它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构:) (https://imghelloworld.osscnbe
如何优雅的使用javascript递归画一棵结构树
递归和尾递归 简单的说,递归就是函数自己调用自己,它做为一种算法在程序设计语言中广泛应用。其核心思想是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的
《前端实战总结》之使用解释器模式实现获取元素Xpath路径的算法
前端领域里基于javascript的设计模式和算法有很多,在很多复杂应用中也扮演着很重要的角色,接下来就介绍一下javascript设计模式中的解释器模式,并用它来实现一个获取元素Xpath路径的算法。 上期回顾 《前端实战总结》之迭代器模式的N1种应用场景(https://juejin.im/post/6844904008616771591)
前端进阶之从零到一实现单向 & 双向链表
前言 前端工程师对于算法和数据结构这块的知识的掌握程度,是进阶高级工程师的非常重要的标志之一,为了总结一下数据结构和算法方面的知识,笔者今天继续把链表这一块的知识补上,也作为自己知识体系的一个梳理,笔者早在去年就写过一篇关于使用javascript实现二叉树和二叉搜索树的文章,如果感兴趣或者想进阶高级的朋友们可以参考学习一下: JavaScript 中的二
javascript进阶必备的二叉树知识
前言 每当放完小长假,我都会习惯性的反思和复盘一下自己的技术,尤其是端午节。为什么我会写二叉树的文章呢?其实这涉及到程序员的一个成长性的问题。对于03年的前端程序员来说,可能很少有机会涉及到数据结构和算法的工作中,除非去大厂或者做架构相关的工作。但是很多工作23年的前端工程师,业务工作已经相对熟悉了,各种技术或多或少也都使用过,那么在这个阶段,对于每个有
算法笔记:红黑树
红黑树,一种平衡二叉树,最为著名的应用就是C STL中的map,是有序集合最为理想的存储方式之一。除了二叉树所具有的属性之后,红黑树中每个节点多了一个“颜色”属性,可以是红色或者是黑色。一棵红黑树应该满足一下的性质: 1. 每个节点是红色或者黑色的; 2. 根节点是黑色的; 3. 每个叶节点nil是黑色的(使用哨兵节点在删除调整时可以方便不少); 4. 如
React之集成测试 – 测试概览
你可以用像测试其他 JavaScript 代码类似的方式测试 React 组件。现在有许多种测试 React 组件的方法。大体上可以被分为两类: 渲染组件树 在一个简化的测试环境中渲染组件树并对它们的输出做断言检查。 运行完整应用 在一个真实的浏览器环境中运行整个应用(也被称为“端到端(endtoend)”测试)。本章节主要专
浅谈Vue3新特性
Vue3的已发布一段时间了,新的Vue3在语法以及底层都进行了全新的重构,带来了更快的运行速度,更小的构建包,更友好的编程规范,让我们来看看有哪些变化吧。更快传统的虚拟dom算法:组件patch的时候,需要重新创建整个vdom树,然后遍历整棵树进行diff,update...更快的虚拟dom算法,源自编译模板时给予更多的运行时提示:1. 编译模板时对动
手把手教你实现一个Vue无限级联树形表格(增删改)
前言平时我们可能在做项目时,会遇到一个业务逻辑。实现一个无限级联树形表格,什么叫做无限级联树形表格呢?就是下图所展示的内容,有一个祖元素,然后下面可能有很多子孙元素,你可以实现添加、编辑、删除这样几个功能。资源 JavaScript框架:vue.js UI框架:Element UI 源码这里需要重点说明的是,主要使用了递归的算法以及给数
Vue - diff 算法
diff是什么?diff就是比较两棵树,render会生成两颗树,一棵新树newVnode,一棵旧树oldVnode,然后两棵树进行对比更新找差异就是diff,全称difference,在vue里面 diff 算法是通过patch函数来完成的,所以有的时候也叫patch算法⏳ diff 发生的时机diff发生在什么时候呢?当然我们可以说在数据更新的时候发生d
javascript实践教程-01-javascript介绍
本节目标1. 了解javascript是什么。2. 了解javascript能干什么。 内容摘要本篇介绍了javascript是什么,为什么要用javascript,ECMAScript标准是什么等。阅读时间大约510分钟。 javascript是什么?javascript是世界上最流行的脚本语言,因为你在电脑、手机、平板上浏览的所有的网页,以及无数基于HT
javascript实践教程-02-javascript入门
本节目标1. 掌握如何编写javascript代码。2. 掌握javascript的3个弹框。3. 掌握javascript的注释。4. 掌握浏览器的调试工具控制台。 内容摘要本篇介绍了如何在网页上编写js代码,如何引入外部js代码文件,js的3个弹框、注释语法,还有浏览器调试工具的控制台使用。阅读时间1520分钟。 script标签如果我们需要在网页中编写