递归算法转换为非递归算法

递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。

将递归算法转换为非递归算法有两种方法，一种是直接求值（迭代/循环），不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。

{
　　 if(n == 0) return 1;
　　 else
 
    {
　　　 int val = factorial(n - 1);
　　　 return n * val;
　　 }
}
 
转化为尾递归求解：
 
int factorial(int acc, int x)
 
 {　//acc传的值为1。
　　if(x <= 1) return acc;
　　else

    return factorial(x * acc, x - 1);
}
 
　　尾递归的重要性在于当进行尾递归调用时，调用者的返回位置不需要被存在调用栈里。当递归调用返回时，它直接分支到先前已保存的返回地址。因此，在支持尾递归优化的编译器上，尾递归在时间和空间上都比较划算。迭代算法需要一个临时变量，这无疑导致了程序的可读性降低，迭代函数不像递归函数那样需要考虑函数调用的支出，而且对一个线程来说可用的栈空间通常比可用的堆空间要少得多，而递归算法则相对迭代算法需要更多的栈空间！
 
2. 间接转换法
　　该方法使用栈保存中间结果，一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下：

将初始状态s0进栈
　　while (栈不为空)
　　{
　　退栈，将栈顶元素赋给s;
　　if (s是要找的结果) 返回;
　　else {
　　寻找到s的相关状态s1;
　　将s1进栈
　　}
　　}
 
间接转换法在数据结构中有较多实例，如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等，请读者参考主教材中相关内容。