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

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

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

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

二叉树的前序算法:

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()最后才被执行到。

posted @ 2020-12-02 18:43:59
评论加载中...
发表评论