掌握递归（recursion）基本就是懂了编程中的

  • 函数调用栈
  • 作用域链
  • 引用类型、基本类型
    • 传递引用、值传递

反之如果二叉树前序、后序遍历也看不懂的话上边三条知识点并不清楚

递归为什么难懂 forloop是线性的，符合大脑思考，很容易想象到最终的结果 递归的难点在于分治上，分治是树状的，第一眼根本看不到最终值，总是担心是不是会漏掉一些； 人肉做树状递归非常痛苦，而在一般教程上递归上来就是树状递归，斐波那契、汉诺塔、二叉树遍历，这种都是非线性树状的递归，而一般编程基础薄弱的调用栈都说不清楚，别说做一个分治递归了。

而在工程中没用那么多分治树状递归，线性递归已经可以让代码优雅的不得了。

工程代码中递归的实践

转换省市区

需求描述

根据地区编码转换为 省 市 区 例如 地区编码：六位 例如110102 数据表格式 

  1. // 数据出处
  2. // https://github.com/withwz/China-area-data-json.git
  3. export default [{
  4.     "value": "110000",
  5.     "label": "北京市",
  6.     "children": [{
  7.         "value": "110100",
  8.         "label": "北京市",
  9.         "children": [{
  10.                 "value": "110101",
  11.                 "label": "东城区"
  12.             }, {
  13.                 "value": "110102",
  14.                 "label": "西城区"
  15.             }
  16.           ...
  17.      }]
  18.           ...
  19.     }]
  20.         ...
  21.   }]

答案
思路
六位数字的地区编码，前两位是省，中间两位是市，最后两位是县区

  • 如果用循环的话也可以，嵌套三层循环呗，但如果再加上镇、乡、村，难道要嵌套六层循环吗。不够优雅。
  • 递归方案：观察数据，是一个三维数组，每一个数组中的对象都有一个children属性，值是一个同外层数组相同格式的数组，那就又children属性则继续向下走呗，终止条件是走到最后一位地区编码

核心

  • 递归
  • 双指针滑动窗口
  • 字符串是值传递
  • 出栈时返回值 ```typescript /**
    • 根据区代码在area.js中的数据拿到省市区 *
    • @param list 地区
    • @param code 六位地区代码 省 市 区
    • @param start 滑动指针两位两位向前滑
    • @param end 滑动指针
    • @param res 省 市 区 */ function getArea(list: Array, code: string, start: number, 
                  end: number, res: any): any {
      if(end > 6) return res const _code = code.toString().slice(start, end) for (let i = 0; i < list.length; i++) { if (_code === list[i].value.slice(start, end)) {
      res = res + list[i].label + ' '
if (list[i]?.children !== undefined) {
    return getArea(list[i].children, code, start + 2, end + 2, res)
  } else {
    return res
  }
}
}
      }

getArea(area, record, 0, 2, ‘’)

<a name="bCffx"></a>
### 扁平化数组
**描述**
> [1, [2, [3, [4]], 5]] ==> [1, 2, 3, 4, 5]

思路

- 数组是引用传递，不会因为进入新调用栈或者出栈而内容改变；
- 如果是数组则继续向下走
```javascript
function isArrType(params) {
    return Object.prototype.toString.apply(params) === '[object Array]'
}

function flatten(arr, ans) {
    for (const iter of arr) {
        if (isArrType(iter) === true) {
            flatten(iter, ans)
        } else {
            ans.push(iter)
        }
    }
    return ans
}

// 测试
let arr = [1, [2, [3, [4]], 5]]
const res = flatten(arr, [])
console.log("res:", res)

总结

递归就是函数调用自己调自己；
常见应用做法是

  • js中可以通过数组对象是引用传递，进入新的调用栈中不会重置对象值的特性不断修改完善值，思想可以参考先序遍历；
  • 也可以把结果返回出来，在最顶层调用完毕后，最顶层调用栈返回给第二层，第二层给第三层…第四层…第五层，在函数出栈的时候不断修改完善值，思想同后续遍历差不多。
    • 比如一个基本类型的字符串，在递归中不断的传递