在coursera上学数据结构与算法，总觉得这一节讲得不清不楚的。虽然原理自己早就明白，可是具体的implementation搞了两三天才终于弄明白怎么做。

简而言之，就是利用一个人工栈来保存现场。模拟系统内堆栈的分配。每进入一个新的递归调用，都要把返回地址、局部变量、参数等信息保存下来。难点在于什么叫做“返回地址”，比如f(x)=f(x+1)+f(x+2)+f(x+3)这个函数，返回类型就有三类。第一类是f(x+1)执行结束，返回到f(x)当中来，此时f(x)还没计算出来，不能返回，而要继续调用f(x+2)和f(x+3)两个函数。从栈的角度来看，这时栈顶是f(x)，非但不能弹出，还要修改一下它的局部变量——f(x+1)的返回值此时要用局部变量储存起来；同时，我们还需要再先后将f(x+2)、f(x+3)入栈。

同理，从f(x+2)返回、f(x+3)返回，都是不同的返回类型。考虑到整个递归过程的入口（也是出口）不是返回到上一级函数体，而是直接结束，又是一种新的返回类型，所以加起来一共有4个。

从树的观点来看，递归的过程其实就是一棵不断生长的树。上面那个f(x)=f(x+1)+f(x+2)+f(x+3)函数则可以视为一棵三叉树的后序遍历。从左孩子返回、从中间孩子返回、从右孩子返回，后面都跟随着截然不同的动作，所以有着不同的返回类型。而根节点更为特殊，压根不能视为三个孩子中的某一种。因而加起来一共有4种。

还有一个有趣的地方：后序遍历时，右孩子的返回可能不只返回一层。比如从f(x+3)返回到f(x)，此时f(x+1)、f(x+2)、f(x+3)都有了，立刻可以得出f(x)的值来。如果x就是根节点，那么整个递归就结束了。如果x不是根节点，而是f(y)=f(y+1)+f(y+2)+f(y+3)中的某个节点，那么立刻又要继续返回了。前序、中序的情况相比也可依次类推。