递归与尾递归简单来说，递归就是函数调用自身，在编程语言中被广泛用作算法。它的核心思想是将一个大而复杂的问题逐层转化为与要解决的原始问题相似的较小规模的问题。通常，递归需要边界条件、递归前向阶段和递归返回阶段。当不满足边界条件时，递归前进；当满足边界条件时，递归返回。但是作为一个合格的程序员，我们也应该知道，递归算法的效率不如普通循环等常用算法。所以应该尽量避免递归，除非没有更好的算法或者特定的情况，什么时候递归更合适。在递归调用的过程中，系统开辟了一个栈来存放返回点和每一层的局部量，递归次数过多容易造成栈溢出。这时候就需要用到尾递归，即函数中所有的递归调用都出现在函数的末尾。对于尾递归，由于只有一条调用记录，因此永远不会出现“栈溢出”错误。functionfactorial(n){if(n===1)return1;returnn*factorial(n-1);}factorial(5)//120需要保存最多n个调用栈，复杂度O(n)，如果我们使用尾递归：functionfactorial(n,total=1){if(n===1)returntotal;returnfactorial(n-1,n*total);}factorial(5)//120这里只需要保存一个调用栈时间，复杂度O(1)。通过这个案例，你是不是渐渐明白了它的本质？接下来介绍几个常用的递归应用案例，然后实现本文标题切出的树。递归的常见应用案例1.数组求和对于已知数组arr，求arr中各项的和。functionsumArray(arr,total){if(arr.length===1){returntotal}returnsum(arr,total+arr.pop())}letarr=[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,F(n)=F(n-1)+F(n-2)(n>=3,n∈N*)现代物理学、准晶体结构、化学等，斐波那契数列都有直接的应用。接下来我们用js实现一个求第n个斐波那契数列的方法：//斐波那契数列functionfactorial1(n){if(n<=2){return1}returnfactorial1(n-1)+factorial1(n-2)}//经过尾递归优化函数factorial2(n,start=1,total=1){if(n<=2){returntotal}returnfactorial2(n-1,total,total+start)}通过尾递归优化后的函数可以知道每次调用函数本身，都会传入更新后的初始值和最终结果，通过回溯可以得到最终结果。3.Factorial上面提到了Factorial，如果你想回顾，请向上滚动。4、省市级联多级联动省市级联多级联动方法的本质是生成结构化数据结构。element或者antd中都有对应的实现，这里就不过多介绍了。5.深拷贝深拷贝的例子大家都很常见。这里只是一个简单的实现思路：(target[key]);}returncloneTarget;}else{returntarget;}};6.阶梯问题一共有n步，一次只能走一个或两步，问有多少种方法可以走完这一步。n=1;result=1-->1n=2;result=2-->112n=3;result=3-->1111221...如果第一步是1步，我们可以找到剩下的n-1在台阶上行走的方式；若第一步走2步，则由上述规则可知，其余步有n-2种行走方式；那么一共有fn(n-1)+fn(n-2)种方式移动functionsteps(n){if(n<=1){return1}returnsteps(n-1)+steps(n-2)}7.对象数据格式化的问题是我曾经面试过阿里笔试题，问题是如果服务端返回一个嵌套对象，对象键名大小写不确定，如果键名统一小写.letobj={a:'1',b:{c:'2',D:{E:'3'}}}转化为：letobj={a:'1',b:{c:'2',d:{e:'3'}}}//代码实现函数keysLower(obj){letreg=newRegExp("([A-Z]+)","g");for(letkeyinobj){if(obj.hasOwnProperty(key)){lettemp=obj[key];if(reg.test(key.toString())){//将修改后的属性名重新赋值给temp，并在对象中添加一个转换后的属性tempobj=obj[key.replace(reg,function(result){returnresult.toLowerCase()})]=obj[key];//删除之前大写的key属性deleteobj[key];}//如果属性是对象或者Array,重新执行函数if(typeoftemp==='object'||Object.prototype.toString.call(temp)==='[objectArray]'){keysLower(temp);}}}returnobj;};具体过程注释和思路都写在代码里了，有兴趣的可以自己研究下。8.遍历目录/删除目录这里我们使用node来删除一个目录。已有的节点API确实有删除目录的功能，但是如果目录中有文件或子目录，fs.rmdir&&fs.rmdirSync是无法删除的，所以先删除目录中的文件，再删除文件夹.functiondeleteFolder(path){varfiles=[];if(fs.existsSync(path)){//如果目录存在files=fs.readdirSync(path);files.forEach(function(file,index){varcurPath=path+"/"+file;if(fs.statSync(curPath).isDirectory()){//如果是目录，则递归deleteFolder(curPath);}else{//删除文件fs.unlinkSync(curPath);}});fs.rmdirSync(路径);}}9.绘制分形图形通过递归，我们可以在图形上有更多的自由度，但记住，这不是最好的选择。我们可以借助一些工具和递归的思想来实现上述的分形模式。10.Flatteningarray数组扁平化其实就是将一个嵌套的数组展开成一个数组，如下例：leta=[1,2,3,[1,2,3,[1,2,3]]]//becomeleta=[1,2,3,1,2,3,1,2,3]//具体实现函数flat(arr=[],result=[]){arr.forEach(v=>{if(Array.isArray(v)){result=result.concat(flat(v,[]))}else{result.push(v)}})returnresult}flat(a)当然这只是作者的实现之一way，更多的实现方式等你来探索。使用递归绘制自定义样式的结构树通过上面的介绍，相信大家对递归及其应用有了一个基本的概念，接下来我将带大家一步步用递归绘制结构树。效果图：该图是根据目录结构生成的目录树图，广泛应用于很多应用场景。接下来我们看一下它的实现过程：constfs=require('fs')constpath=require('path')//遍历目录/生成目录树函数treeFolder(path,flag='|_'){varfiles=[];if(fs.existsSync(path)){files=fs.readdirSync(path);files.forEach(function(file,index){varcurPath=path+"/"+file;if(fs.statSync(curPath)。isDirectory()){//recurse//obj[file]=treeFolder(curPath,{});console.log(flag,file)treeFolder(curPath,''+flag)}else{//obj['--']=fileconsole.log(flag,file)}})//returnobj}}treeFolder(path.resolve(__dirname,'./test'))test是我们建的测试目录，如下：我们实现了一个小的只需几行代码即可生成结构树的应用程序。感觉递归有意思吗？在这个函数中，第一个参数是目录的绝对路径，第二个是标识符，决定了我们生成的分支的样式，我们可以自定义不同的样式。
