递归和尾递归

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

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

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

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

  <pre style="font-size: 16px;font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace;margin-top: 10px;margin-bottom: 10px;overflow: auto;border-radius: 5px;box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;color: rgb(0, 0, 0);text-align: left;background-color: rgb(255, 255, 255);">function factorial(n) {   if (n === 1) return 1;   return n * factorial(n - 1); } factorial(5) // 120 </pre>

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

  <pre style="font-size: 16px;font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace;margin-top: 10px;margin-bottom: 10px;overflow: auto;border-radius: 5px;box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;color: rgb(0, 0, 0);text-align: left;background-color: rgb(255, 255, 255);">function factorial(n, total = 1) {   if (n === 1) return total;   return factorial(n - 1, n * total); } factorial(5) // 120 </pre>

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

  递归的常用应用案例1. 数组求和

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

  <pre style="font-size: 16px;font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace;margin-top: 10px;margin-bottom: 10px;overflow: auto;border-radius: 5px;box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;color: rgb(0, 0, 0);text-align: left;background-color: rgb(255, 255, 255);">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 </pre>

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

  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个斐波那契数的方法：

  <pre style="font-size: 16px;font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace;margin-top: 10px;margin-bottom: 10px;overflow: auto;border-radius: 5px;box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;color: rgb(0, 0, 0);text-align: left;background-color: rgb(255, 255, 255);">// 斐波那契数列 function factorial1 (n) {     if(n  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  {         if(Array.isArray(v)) {             result = result.concat(flat(v, []))         }else {             result.push(v)         }     })     return result } flat(a) </pre>

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

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

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

  该图形是根据目录结构生成的目录树图，在很多应用场景中被广泛使用，接下来我们就来看看他的实现过程吧：

  <pre style="font-size: 16px;font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace;margin-top: 10px;margin-bottom: 10px;overflow: auto;border-radius: 5px;box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;color: rgb(0, 0, 0);text-align: left;background-color: rgb(255, 255, 255);">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')) </pre>

  test为我们建的测试目录，如下：

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