尾递归算法转化成迭代算法

所有递归算法都可以转化成非递归算法吗？

是的。一般的转换思路，无非是利用栈模拟操作系统的工作过程。

不过通用方法太过复杂，我们仅讨论一类只在递归函数的尾部调用递归，称之为尾递归，尾递归非常容易转换为非递归算法。这是因为尾递归中的非递归语句的执行次序与函数的调用次序相同，每当有一个函数执行时，将它入栈，当他出栈后就可以执行它所对应的非递归语句。

二叉树的前序算法：

void PreOrder(Tree t)
{
    if(!t) return;
    visit(t);
    PreOrder(t->lChild);
    PreOrder(t->rChild);
}

转换为迭代版本：

void PreOrder(Tree t)
{
    if(t) stack.push(t);  //根节点入栈
    while(!stack.empty()){
        t = stack.pop();
        visit(t->data);   //非递归语句在出栈后执行
        if(t->rChild) stack.push(t->rChild);  //右孩子先入后出
        if(t->lChild) stack.push(t->lChild);
    }
}

非尾递归显然不能这么做，因为在非尾递归中，visit()的执行次序与函数的调用次序没啥关系，甚至有可能函数先调用visit()最后才被执行到。