如何使用堆栈将以下代码替换为非递归代码？

Question

这是一个有限状态机：

private int recursive(int rc, int pc, int sc) {
    for (;;) {
        Instruction actual = program[rc][pc];
        switch (actual.type) {
            case FIRST:
                if (sc >= input.length || input[sc] != actual.c1) return -1;
                pc++; sc++;
                continue;
            case SECOND:
                pc = actual.n1;
                continue;
            case THIRD:
                int result = recursive(rc, actual.n1, sc);
                if (result != -1) return result;
                pc = actual.n2;
                continue;
            case FOURTH:
                result = recursive(actual.n1, 0, sc);
                if (result == -1) return -1;
                pc++; sc = result;
                continue;
            case FIFTH:
                if (sc == input.length) return sc;
                return -1;
        }
        return -1;
    }
}

感谢您的帮助。

Answer 1

考虑一下递归。当您递归调用方法时，您实际上调用了方法并将同一方法的先前调用的状态存储在某处。你把这个状态存储在哪里？答案是“在堆栈中”。但是当您使用递归调用时，系统会为您管理堆栈。

所以，你必须自己管理它。这意味着以下内容。在第一次方法调用之前创建堆栈。更改方法的签名：它应该接受堆栈作为参数。堆栈应该包含您的状态。如果不检查代码，它可以是原始对象，也可以是复杂对象。如果您需要复杂的对象，请创建自己的类 State，它将保存所有需要的信息。

我希望这已经足够了。祝你好运！