在基于栈的运行时环境中,每次函数调用都会在栈顶产生一个新的桢,并且将控制权交给被调用的函数;当被调用的函数返回时,相对应的桢从栈顶弹出,控制权将重新交回给调用方,调用方从函数调用的下一条语句继续执行。桢中保存的信息,主要分为两类:
返回值可以通过寄存器来传递,也就是说,被调用的函数在返回时,将返回值写进寄存器,调用方再从寄存器获取返回值。
递归调用就是一个函数直接或间接地调用自身,因此可以通过模拟桢 和 栈来消除递归。
这里需要说明的是,消除递归不一定非要使用栈,因为递归只是算法设计的一种方式,比如,对于斐波那契数列,可以使用递推的方式来实现:
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 BaseFramepreviousFrame; 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
的消递归实现。它的执行流程主要是:
递归返回段
,首先将这个执行结束的桢对象从栈顶弹出,然后使用address 和 value保存该桢对象的返回地址 和 返回值,在下次循环时,就会从位置address继续执行前一个桢对象
递归前进段
,首先将这个新的桢对象,压入栈顶,然后将address 和 value 清零,在下次循环时,就会从位置0开始执行这个新的桢对象1,当函数间接的调用自身时,比如f 调用了 g,g 又调用了 f,此时: