使用循环和栈消除递归调用

相关知识


基本思路

在基于栈的运行时环境中,每次函数调用都会在栈顶产生一个新的桢,并且将控制权交给被调用的函数;当被调用的函数返回时,相对应的桢从栈顶弹出,控制权将重新交回给调用方,调用方从函数调用的下一条语句继续执行。桢中保存的信息,主要分为两类:

  • 相对应的函数 执行过程中的状态:实参和局部变量
  • 恢复调用方所需的信息:前一个桢的桢指针和返回地址

返回值可以通过寄存器来传递,也就是说,被调用的函数在返回时,将返回值写进寄存器,调用方再从寄存器获取返回值。
递归调用就是一个函数直接或间接地调用自身,因此可以通过模拟桢 和 栈来消除递归。

这里需要说明的是,消除递归不一定非要使用栈,因为递归只是算法设计的一种方式,比如,对于斐波那契数列,可以使用递推的方式来实现:

    public static int fibo(int n) {
        if (n <= 2) return n;

        int first = 1, second = 2, result = 0;
        for (int i = 3; i <= n; ++i) {
            result = first + second;
            first = second;
            second = result;
        }   

        return result;
    }    

    public static int fiboRecursion(int n) {
        if (n <= 2) return n;
        return fiboRecursion(n - 1) + fiboRecursion(n - 2); 
    } 


但是使用栈,一定可以将递归消去。


代码实现

  • 使用对象模拟桢
    • 使用成员变量 保存 函数的“实参”、“局部变量” 以及 “前一个桢对象的引用”
    • 使用一个整型的成员变量 保存 “返回地址”
      • “实参”、“返回地址”、“前一个桢对象的引用”,需要在构造桢对象时就进行初始化
      • “局部变量”在 执行过程中,进行初始化
    • 使用一个 成员方法 代替 递归函数,且该成员方法需要满足:
      • 支持从指定的位置开始运行,运行过程中产生的中间结果保存到“局部变量”中,以便该方法下次从某一位置继续执行时,依然可以使用它们
      • 在发生递归调用的时,返回 一个 “桢对象”
      • 运行结束时,保存运行结果,并且返回null,返回null即意味着执行结束,“桢对象”会从栈顶弹出
  • 模拟 运行时栈
    • 使用 Stack数据结构 和 循环 模拟 运行时栈的行为

下面用汉诺塔这个例子,进行说明:

import java.util.Stack;

abstract class BaseFrame<T> {  
    private int returnAddress;
    private BaseFrame<T> previousFrame;
    private T result;

    public BaseFrame(int returnAddress, BaseFrame<T> previousFrame) {
        this.returnAddress = returnAddress;
        this.previousFrame = previousFrame;
    }

    public void setResult(T result) {
        this.result = result;
    }

    public int getReturnAddress() {
        return returnAddress;
    }

    public BaseFrame<T> getPreviousFrame() {
        return previousFrame;
    }

    public T getResult() {
        return result;
    }
}

class HanoiFrame extends BaseFrame<Object> {  
    private int n;
    private char A, B, C;

    public HanoiFrame(int n, char A, char B, char C, int returnAddress, HanoiFrame previousFrame) {
        super(returnAddress, previousFrame);
        this.n = n;
        this.A = A; this.B = B; this.C = C;
    }

    public int getN() {
        return n;
    }

    public char getA() {
        return A;
    }

    public char getB() {
        return B;
    }

    public char getC() {
        return C;
    }

    public HanoiFrame execute(int address, Object value) {
        switch (address) {
            case 0:
                if (getN() == 1) {
                    System.out.println("move 1 from " + getA() + " to " + getC());
                    setResult(null);
                    return null;
                }
                return new HanoiFrame(getN() - 1, getA(), getC(), getB(), 1, this);
            case 1:
                System.out.println("move " + getN() + " from " + getA() + " to " + getC());
                return new  HanoiFrame(getN() - 1, getB(), getA(), getC(), 2, this);
            case 2:
                setResult(null);
                return null;
            default:
                throw new RuntimeException("what the fuck");
        }
    }
}

public class HanoiStack {  
    public static void hanoiStack(int n, char A, char B, char C) {
        Stack<HanoiFrame> stack = new Stack<HanoiFrame>();
        stack.push(new HanoiFrame(n, A, B, C, -1, null));
        int address = 0;
        Object value = null;
        HanoiFrame nextFrame, activeFrame;

        while (!stack.empty()) {
            activeFrame = stack.peek();
            nextFrame = activeFrame.execute(address, value);
            if (nextFrame == null) {
                activeFrame = stack.pop();
                address = activeFrame.getReturnAddress();
                value = activeFrame.getResult();
            } else {
                stack.push(nextFrame);
                address = 0;
                value = null;
            }
        }
    }

    public static void hanoi(int n, char A, char B, char C) {
        if (n == 1) {
            System.out.println("move 1 from " + A + " to " + C);
            return;
        }
        hanoi(n - 1, A, C, B);
        System.out.println("move " + n + " from " + A + " to " + C);
        hanoi(n - 1, B, A, C);
    }

    public static void main(String[] args) {
        hanoiStack(3, 'A', 'B', 'C');
        System.out.println("==========");
        hanoi(3, 'A', 'B', 'C');
    }
}


其中,方法hanoiStack是递归方法hanoi的消递归实现。它的执行流程主要是:

  1. 第一个桢对象入栈,并使用局部变量address保存桢对象的返回地址,value保存桢对象的返回值,初始时,address是0,也就说,桢第一次都是从位置0开始执行
  2. 获取栈顶的桢对象,并使用address 和 value调用该桢对象的execute方法
    • 如果execute方法返回null,说明进入了递归返回段,首先将这个执行结束的桢对象从栈顶弹出,然后使用address 和 value保存该桢对象的返回地址 和 返回值,在下次循环时,就会从位置address继续执行前一个桢对象
    • 如果execute方法返回 一个桢对象,说明进入了递归前进段,首先将这个新的桢对象,压入栈顶,然后将address 和 value 清零,在下次循环时,就会从位置0开始执行这个新的桢对象
  3. 重复过程2,直到栈空,value的值就是整个递归调用的返回值

F & Q

1,当函数间接的调用自身时,比如f 调用了 g,g 又调用了 f,此时:

  • 可以通过将 g 内联到 f 的方式,将其转换成 函数直接调用自身
  • 也可以实现两种“桢类型”

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: