通过一些常见场景,梳理递归相关的数据结构和算法,如列表和树互转、驼峰和下划线互转。
主要的数据结构是
- Array
- Map
- Set
Array 比较特殊,有 push、pop、shift、unshift 等方法,能够当作栈使用。
Map 映射操作也很常见,减少寻址的时间复杂度(经常使用 Object 来实现类似功能)。
常用到的算法是
Iteration(迭代)DFS(深度优先搜索)
js 原生语法有许多迭代器,用来处理数据,如数组的 forEach、for of,对象的 entries()、keys()。
递归能实现的迭代通常来说也可以实现,如数组扁平化。递归通常来说语义更简洁,但是性能更差;迭代代码可能更复杂不好理解,但是性能更好。
仓库文件命名遵循如下规则,
| Name | value | Description |
|---|---|---|
| A | Array | 操作包含数组 |
| MSO | Map、Set、Object | 操作包含映射、集合、对象 |
| I | Iteration | 操作包含迭代 |
| R | Recursion | 操作包含递归 |
如 A-I 表示重点是用到数组以及迭代方法,
A-R 表示重点使用到数组以及递归方法(尽管中间过程也借助了迭代的能力)
遵循数据结构在前,操作方法在后