了解递归：普通函数递归和非递归栈式实现之间的区别

相关链接 ： 递归和栈的关系

以树的遍历为例

先序遍历：

伪代码

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的节点对应的栈帧就有了方向，知道要把右子包成一个栈帧入栈

其实在知道左子节点入栈了，但右子节点未入栈后，没必要保存当前栈帧，因为上述伪代码对右子节点的递归是尾递归，即当前函数递归调用当前函数，但是并不期待这个递归调用

给当前的函数带来些什么，递归调用也用不到当前函数栈帧。所以可以直接弹出。

上图可简化：