使用javascript递归绘制结构树的优雅示例代码

递归和尾部递归

简单来说，递归就是函数调用自己。递归作为一种算法，在编程语言中被广泛使用。它的核心思想是将一个大而复杂的问题转化为一个类似于原问题的小问题。一般来说，递归需要边界条件、递归前向阶段和递归返回阶段。当边界条件不满足时，递归推进；当边界条件满足时，递归返回。

但是，作为一个合格的程序员，我们也应该知道递归算法的效率不如普通循环等普通算法。因此，应该尽可能避免递归，除非没有更好的算法或者在特定情况下递归更合适。在递归调用的过程中，系统会打开一个栈来存储各层的返回点和局部量，递归过多容易造成栈溢出。

这时，我们需要使用尾部递归，即一个函数中的所有递归调用都出现在函数的末尾。对于尾部递归，因为只有一个调用记录，所以“堆栈溢出”错误永远不会发生。

例如，让我们实现阶乘。如果我们使用普通递归，实现将是这样的：

函数阶乘(n) { if (n===1)返回1；返回n *阶乘(n-1)；}阶乘(5) //120最多需要保存n个调用栈，复杂度为O(n)。如果我们使用尾部递归：

函数阶乘(n，total) { if (n===1)返回total；返回阶乘(n - 1，n * total)；}阶乘(5) //120此时只需要保存一个调用栈，复杂度为O(1)。通过这个案例，你是否逐渐理解了它的本质？接下来，我将介绍几个常用的递归应用案例，然后实现本文标题所裁剪出的树。

递归的常见应用案例

1.阵列求和

对于已知的数组arr，求arr项的和。

函数sumArray(arr，total){ if(arr . length===1){ return total } return sum(arr，total arr . pop())}让arr=[1，2，3，4]；SumArray(arr，arr[1]) //10该方法将一个数组参数和一个初始值传递给函数，即数组的第一项，通过迭代实现数组求和。

2.斐波那契数列

斐波那契数列，也叫黄金分割数列，指的是这样一个数列：1，1，2，3，5，8，13，21，34，…数学上，斐波那契数列是通过递归定义的如下：F(1)=1，f (2)=1接下来，我们用js实现一个求第n个斐波那契数的方法：

//斐波那契数列函数阶乘1 (n) {if (n=2) {return 1} return阶乘1 (n-1)阶乘1(n-2)}//函数阶乘2 (n，start=1，Total=1){ if(n=2){ return Total } return阶乘2 (n-1，Total，total start)}从尾部递归优化的函数可以知道，每次调用函数本身，都会传入更新的初始值和最终结果，通过回溯得到最终结果。

3.阶乘

上面已经提到了阶乘。如果你想复习，请查阅。

4.省市级联多级联动

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

5.深度复制

深度复制的例子已经司空见惯，这里只给出一个简单的实现思路：

函数克隆(目标){ if(type of target==' object '){ let cloneTarget=array . isarray(目标)？[] : {};for(const key in target){ cloneTarget[key]=clone(target[key])；}返回cloneTarget} else {返回目标；}};6.爬梯子

总共有n步，一次只能走一两步。问这一步走了多少路。

n=1；结果=1-1n=2；结果=2-11 2n=3；结果=3 - 111 12 21.如果第一步走了一步，从上面的规则可以发现，剩下的几步有n-1种走法；如果你在第一步走两步，你会发现从上面的规则中有n-2种方法可以走完剩下的步骤；然后总共有fn(n-1) fn(n-2)个函数步骤(n) {if (n=1) {return 1}个返回步骤(n-1)个步骤(n-2)} 7。对象数据格式

这个问题是对阿里曾经的一次采访。问题是如果服务器返回嵌套对象，对象键名的大小写不确定，键名统一的话会小写。

Letobj={a:' 1 '，b: {c:' 2 '，d: {e:' 3'}}转换如下：letobj={a:' 1 '，b: {c:' 2 '。D: {e: '3'} }}//Code实现功能键较慢(obj) {let reg=new regexp ('([a-z])'，' g '；for(let key in obj){ if(obj . hasown property(key)){ let temp=obj[key]；If (reg测试(键。tostring())){//将修改后的属性名重新分配给temp，并添加转换后的属性temp=obj [key。replace (reg，function (result) {return result。to lower case()}))]=对象obj中的obj[key]；//删除之前大写的键属性[key]；}//如果属性是对象或数组，则重新执行函数if(类型为temp==' object ' | | object . prototype . tostring . call(temp)='[object array]'){ key slow(temp)；} } }返回obj};具体的流程和思路已经在代码中注释了。如果你感兴趣，你可以自己研究。

8.遍历目录/删除目录

我们这里用node来删除一个目录，现有的node API确实有删除目录的功能。但是如果目录中有文件或者子目录，fs.rmdir fs.rmdirSync是不能删除的，所以我们必须先删除目录中的文件，然后再删除文件夹。

函数deleteFolder(路径){ var files=[]；If(fs.existsSync(路径)){//如果目录存在，files=fs.readdirSync(路径)；files.forEach(函数(文件，索引){ var curPath=path/' file；If (fs。statsync (curpath)。is directory()){//如果是目录，递归删除文件夹(curPath)；} else {//删除文件fs . unlink sync(curPath)；} });fs.rmdirSync(路径)；}}9.绘制分形图形

通过递归，我们可以在图形上有更多的自由，但请记住，这不是最好的选择。

我们可以用一些工具和递归的思想来实现上面的分形图案。

10.将阵列展平

数组展平实际上是将嵌套数组展开成一个数组，如下例所示：

让a=[1，2，3，[1，2，3，[1，2，3]]//变成让a=[1，2，3，1，2，3]//实现函数flat(arr=[]，Result=[]) {arr。foreach (v={if (array。ISARRAY(v)){结果=结果。concat (flat (v，[]))} else {result。push (v)}})返回结果} flat (a)，当然这只是我的一个实现。

递归绘制自定义样式的结构树

通过以上的介绍，我想大家对递归及其应用都有了一个基本的概念。接下来，我将带您一步一步地用递归绘制结构树。

渲染：

该图是根据目录结构生成的目录树图，广泛应用于许多应用场景。让我们看看它的实现过程：

const fs=require(' fs ')const path=require(' path ')//遍历目录/生成目录树函数treefolder (path，flag=' | _ '){ var files=[]；if(fs.existsSync(路径)){ files=fs.readdirSync(路径)；files.forEach(函数(文件，索引){ var curPath=path/' file；if(fs.statSync(curPath))。isDirectory()){//recurse//obj[file]=tree folder(curPath，{ })；Console.log (flag，file) treefolder (curpath，' ' flag)} else {//obj['-']=file console . log(flag，file)} })//returnobj } } tree folder(path . resolve(_ _ dirname，'，

我们用10多行代码实现了一个生成结构树的小应用程序。你认为递归有趣吗？在这个函数中，第一个参数是目录的绝对路径，第二个参数是标记，它决定了我们生成的分支的样式。我们可以定制不同的款式。

摘要

以上就是本文的全部内容。希望本文的内容对大家的学习或工作有一定的参考价值。谢谢你的支持。