相关链接 ： 递归和栈的关系
以树的遍历为例
先序遍历：
伪代码
void preView(Node node){
print(node.value); // 1
if(node.left != null){
preView(node.left); // 2
}
if(node.right != null){
preView(node.right); // 3
}
}
如果我们用函数栈帧的思想，每调用一个函数，就把一个栈帧入栈
这里的问题就是：栈帧无法为我们提供足够的信息，让我们正确的继续用栈执行递归。
如果编译器编译上述的伪代码，那么在函数栈帧中会保存要返回的地址。在上述情景中，节点2的栈帧中不应该只保存节点2，应该还要保存2执行到第几行了。
继续下去是要执行第二行还是执行第三行（返回的地址）。但是软件实现一般不这么做，也不能这么做，因为我们用纯代码不用嵌入汇编的话，
很难做到像用ret这样的指令一样改变IP寄存器
可以选择在栈帧中保存一个标志，来标识要向左走（递归调用左子节点，代码中行2）还是向右（递归调用右子节点，代码中行3）走，还是说都走过了，要弹出（即已经执行了代码中行2，行3，函数执行完毕返回）。比如一个int变量，如果左子节点已入栈，但右子未入栈，就标记为1。0表示均未递归调用左右子节点，2表示都调用过。
递归子函数的栈帧弹出后，返回到针对当前节点的栈帧：有以下情况
0，如果这个int变量为0，则左右子节点都未被递归调用
1，如果这个int变量为1，则把右子节点对应栈帧入栈，并且把当前栈帧中这个int变量修改成2
2，如果这个int变量为2，则直接把当前栈帧弹出
于是当2的节点对应栈帧出栈后，5的节点对应的栈帧就有了方向，知道要把右子包成一个栈帧入栈
其实在知道左子节点入栈了，但右子节点未入栈后，没必要保存当前栈帧，因为上述伪代码对右子节点的递归是尾递归，即当前函数递归调用当前函数，但是并不期待这个递归调用
给当前的函数带来些什么，递归调用也用不到当前函数栈帧。所以可以直接弹出。
上图可简化：
原文：https://www.cnblogs.com/lqlqlq/p/13257811.html