递归算法之后序遍历与执行栈之间的理解

前言

我们开发中肯定遇到过表格的开发，以antd举例来说，tree Table有父级子级的深层树状结构
可能是
1.[{children: [...]}]这种list children的形式，
也可能是
2.[{id: 1}, {parentId: 1}]构成的{id: 1, children: { parentId: 1 }}这种形式，

对于1使用递归遍历数据即可，对于2则需要先由打平数据转化为1的结构再递归遍历，由此我们可以看出不管是哪种数据结构我们都需要使用最基本的遍历，下面就来讲讲递归算法与执行栈中的联系。

执行栈

看过事件循环(event loop)的朋友肯定知道执行栈这个概念，我们的js代码在编译完成后会被js引擎按照从上到下的顺序压入执行栈去执行，遇到异步任务根据异步任务的种类分别丢入宏任务队列和微任务队列，这里打个比方有一个js文件中从上到下写了两个函数fna和fnb，分别调用fna()和fnb()，依次压入栈后执行的是fna，执行完毕函数返回抛出执行栈，在压入fnb...，这就包含了执行栈的压入和抛出的概念last in first out简称（LIFO），调用一个函数就会把函数压入执行栈去执行，这里从网上扣了一张动图帮助理解：

执行栈动图.gif

那么递归算法和执行栈有什么关系呢？

递归

递归算法在我们日常编码中再常见不过了，写递归无非需要两种条件:
1.处理同一件事情需要相同的处理方法
2.终止条件
例如: 我需要打印这组数据中所有的name


const list = [
{name: '张三',
 children: [
  {name: '李四', children: []},
  {name: '王五', children: []},
  ]
}]

递归可以这么写

function printName(dataSource) {
  dataSource.forEach(item => 
    // 这里是终止条件 满足条件继续递归
    if(item?.children && item.children instanceOf Array) {
       printName(item?.children);
     }
    console.log(`我的名字叫${item?.name}`);
  );
}
printName(list);

从上面的递归方法中可以看到，当满足一定条件后再forEach循环中继续调用printName，前面我们提到调用函数会把函数压入执行栈，所以这里js不断把满足条件的printName压入执行栈，知直到所有满足条件的函数压入栈完毕，执行栈按照LIFO的顺序分别打印出'王五'、'李四'和'张三。
到这里我们知道了递归是不断把可执行的函数塞入执行栈，再按照LIFO的方式从栈顶往栈低执行。
那执行栈和递归的关系我知道了，这跟后续遍历有什么关系吗？

后序遍历

学过数据结构与算法课程的朋友肯定知道二叉树的概念，对二叉树的遍历我们有三种方式：
1.前序遍历(根左右) 2.中序遍历(左根右) 3.后序遍历(左右根)
我们这里主要讲后序遍历，前面我们看到递归不断把函数压入执行栈，再从上到下执行弹出，这个过程就是后序遍历

总结

执行栈是有一定内存空间的，也就是我们常说的RAM运行内存，所以当数据量大于一定阀值时，过多的待执行函数被放到运行内存中可能会造成内存溢出的问题，这也不难理解为什么有的工程开发到一定阶段，node起服务会因为内存溢出起服务失败了。
我们通过不断学习基础知识点并把知识点串联到一起会明白很多道理，有助于我们自我提升。

最后编辑于：2021.10.03 10:50:31