相关知识


基本思路

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

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

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

    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); 
    } 

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


代码实现

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

import java.util.Stack;

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

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

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

    public int getReturnAddress() {
        return returnAddress;
    }

    public BaseFrame 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 stack = new Stack();
        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方法
  3. 重复过程2,直到栈空,value的值就是整个递归调用的返回值

F & Q

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


Read Also