相关知识

• 关于递归调用，请查看这篇文章。
• 关于基于栈的运行时环境，请查看这篇文章。

基本思路

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

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

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

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

    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 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方法
   • 如果execute方法返回null，说明进入了递归返回段，首先将这个执行结束的桢对象从栈顶弹出，然后使用address 和 value保存该桢对象的返回地址 和 返回值，在下次循环时，就会从位置address继续执行前一个桢对象
   • 如果execute方法返回 一个桢对象，说明进入了递归前进段，首先将这个新的桢对象，压入栈顶，然后将address 和 value 清零，在下次循环时，就会从位置0开始执行这个新的桢对象
3. 重复过程2，直到栈空，value的值就是整个递归调用的返回值

F & Q

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

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

Read Also

• 斐波那契数列的消递归实现（Golang 版本）：http://timd.cn/eliminate-recursive/fibo_stack.go.txt