问题：自己管理栈来实现递归程序。找出通用的改写方法。
解答思路：模拟递归程序的执行过程，并每次将递归当前层的调用现场手动压入栈和弹出栈。
分析：
举一个简单的例子来分析递归的调用过程,如factor(n) = n*factor(n-1).
递归程序如下：
int factor(int n){ if(n == 1) return 1; return n*factor(n-1);} 其执行过程如下：
由图可知，递归函数每一层的调用现场将被访问两次，并且符合“后进先出”的特点,这也是为什么要用栈。
那么我们分析stage 0这一步都做了些什么：
上图说明了在每一层，stage 0时执行的就是递归函数里，递归调用下一层的语句之前的代码。其事实也很明显，不再赘述。同样，stage 1时，由下向上执行的是递归函数里，递归调用下一层的语句之后的代码。
依此分析，将原递归函数分为如下片段：
好了，总结下上面的分析：
要将递归转为非递归，首先需要保存每一层的状态信息，包括函数参数，函数返回值等。每一层还有可能处于2个(或者更多，后面举例)不同的stage，这个信息也要记录下来。然后就是依据递归函数的调用位置(也就是入栈时刻)分别处理，在入栈前处理stage 0的代码，入栈后处理stage 1的代码。
解答：
现在来写对应的非递归程序：
1.首先定义一个结构体，保存每一层的递归调用现场。
结构体包含：
1)递归函数的参数；
2)如果函数有返回值，也要包括一个返回值类型。
3)一个stage变量，指示当前处于哪个stage。
struct SnapShort{ int n; int retVal; int stage;}; 2.定义一个栈，来保存这个结构体。
stackss;
3.将初始状态入栈。
SnapShort currentSnap;currentSnap.n = n;currentSnap.retVal = 0;currentSnap.stage = 0;ss.push(currentSnap);
4.while循环，模拟整个递归过程。
int retVal = 0;//定义一个变量保存函数的最终返回值。while(!ss.empty()){ currentSnap = ss.top(); ss.pop(); switch(currentSnap.stage) { case 0: //执行递归下一层之前的代码 if( currentSnap.n == 1) { retVal = 1; continue; } currentSnap.stage = 1; ss.push(currentSnap); SnapShort newSnap; newSnap.n = currentSnap.n-1; newSnap.retVal = 0; newSnap.stage = 0; ss.push(newSnap); break; case 1: //执行递归下一层之后的代码 currentSnap.retVal = currentSnap.n * retVal; retVal = currentSnap.retVal; break; }} return retVal;
一点注释：
在while循环里，首先将当前状态结构体出栈，分析其处于哪个stage。
如果是stage 0，执行递归函数里属于stage 0的代码。然后将当前状态的stage改为1,并入栈。因为当前层已经处理完。然后创建下一层的状态结构体，初始化对应的值，其stage当然为0，入栈。（也就对应着递归调用下一层的语句。）
如果是stage 1，说明递归已经由下向上执行，处理stage 1对应的代码即可。
----------------------------------华丽的分割线------------------------------------------
例子2：关于多个stage的情况。
汉诺塔问题：托盘A上有N个从小到大的盘子，请借助B的辅助，将它们全部移动到C上。小盘子不能叠在比它大的盘子上。
递归实现很简单：
void hanoi(int n, char a, char b, char c)//初始a为’A', b为‘B’, c为‘C'{ if(n == 1) { cout << a << '->' << c << endl; return; } hanoi(n-1, a, c, b); cout << a << '->' << c << endl; hanoi(n-1, b, a, c);} 非递归实现:
由递归程序可以看到，2次递归调用了下一层的自己。所以会有3个stage。如下：
对应的非递归程序如下：
void nonrecursive_hanoi(int n, char a, char b, char c){ struct SnapShort { int n; char a; char b; char c; int stage; }; stack ss; SnapShort currentSnap; currentSnap.n = n; currentSnap.a = a; currentSnap.b = b; currentSnap.c = c; ss.push(currentSnap); while(!ss.empty()) { currentSnap = ss.top(); ss.pop(); switch(currentSnap.stage) { case 0: if(currentSnap.n == 1) { cout << currentSnap.a << "->" << currentSnap.c << endl; continue; } currentSnap.stage = 1; ss.push(currentSnap); SnapShort newSnap; newSnap.n = currentSnap.n - 1; newSnap.a = currentSnap.a; newSnap.b = currentSnap.c; newSnap.c = currentSnap.b; newSnap.stage = 0; ss.push(newSnap); break; case 1: cout << currentSnap.a << "->" << currentSnap.c << endl; currentSnap.stage = 2; ss.push(currentSnap); SnapShort newSnap2; newSnap2.n = currentSnap.n - 1; newSnap2.a = currentSnap.b; newSnap2.b = currentSnap.a; newSnap2.c = currentSnap.c; newSnap2.stage = 0; ss.push(newSnap2); break; case 2: break; } }}
总结：
本文递归转化为非递归的思路，实际上就是手动去模拟递归的执行过程。本文将递归程序划为几个stage，从而有套路的写出非递归程序，极大简化了编写非递归程序的步骤。
这儿有几个技巧：
1.如果递归函数有返回值，需要在非递归函数while循环外声明一个返回值类型的变量，用于记录最终的返回值。如果在递归程序中函数的返回值有默认值，则声明时，可用此默认值来初始化此变量。而递归程序中的return语句，就对应了非递归程序中，在while循环里的对应位置，对此变量赋值。
2.递归程序中每一句递归调用语句，对应while循环中，某层状态结构体的stage的变化。
备注：
本文的思路很大的借鉴了这篇论文，附链接：