1

关于如何将递归转换为非递归有很多问题，我也可以将一些递归程序转换为非递归形式注意：我使用一种通用的方式（用户定义的堆栈），因为我认为它很容易理解，并且我使用 Java，所以不能使用 GOTO 关键字。

事情并不总是那么顺利，当我遇到回溯时，我被卡住了。例如，子集问题。我的代码在这里：recursive call with loop

当我使用用户定义的堆栈将其转换为非递归形式时。我不知道如何处理循环（在循环中存在递归调用）。

我google了一下发现有很多方法，比如CPS。我知道有一个子集问题的迭代模板。但我只想使用用户定义的堆栈来解决。

有人可以提供一些线索来将这种递归（循环递归）转换为非递归形式（通过使用用户定义的堆栈，而不是 CPS 等）吗？

这是我的代码递归到非递归（Inorder-Traversal），因为递归调用没有循环，所以我可以轻松做到。同样，当具有返回值的递归程序时，我可以使用引用并将其作为参数传递给函数。从代码中，我使用堆栈来模拟递归调用，并使用“状态”变量到下一个调用点（因为 java 不允许使用 GOTO）。

以下是我收集到的信息。似乎所有这些都不满足我提到的问题（有些使用 goto 不允许 java，有些是非常简单的递归意味着没有嵌套递归调用或带有循环的递归调用）。

1旧自治领大学

2代码项目

----------------------------------分割线-------------- ----------------------

谢谢你们。在我发布问题之后......我花了一整夜才弄清楚。这是我的解决方案：非递归子集问题解决方案，代码的注释是我的想法。

总结一下。我之前坚持的是如何处理 foo-loop，实际上，我们可以简单地忽略它。因为我们使用的是loop+stack，所以可以对是否满足条件做一个简单的判断。

4

2 回答 2

0

在您的堆栈上，您是否考虑过推送 i（迭代变量）？通过这样做，当你弹出这个值时，你知道在你压入堆栈之前循环的哪个迭代，因此，你可以迭代到下一个 i 并继续你的算法。

于 2018-01-19T09:51:32.400 回答
0

非负数仅为简单起见。（也没有 IntFunction。）

这里定义的power函数是一个非常简单的例子。

int power(int x, int exponent) {
    if (exponent == 0) {
        return 1;
    } else if (exponent % 2 == 0) {
        int y = power(x, exponent /2);
        return y * y;
    } else {
        return x * power(x, exponent - 1);
    }
}

现在堆栈可以按照与部分结果相反的顺序执行，即您在递归中对结果所做的操作。

int power(final int x, int exponent) {
    Stack<Function<Integer, Integer>> opStack = new Stack<>();
    final Function<Integer, Integer> square = n -> n * n;
    final Function<Integer, Integer> multiply = n -> x * n;
    while (exponent > 0) {
        if (exponent % 2 == 0) {
            exponent /= 2;
            opStack.push(square);
        } else {
            --exponent;
            opStack.push(multiply);
        }
    }
    int result = 1;
    while (!opStack.isEmpty()) {
        result = opStack.pop().apply(result);
    }
    return result;
}

另一种方法是用布尔值“编码” if-else 的两个分支（奇数/偶数指数）：

int power(final int x, int exponent) {
    BooleanStack stack = new BooleanStack<>();
    while (exponent > 0) {
        boolean even = exponent % 2 == 0;
        stack.push(even);
        if (even) {
            exponent /= 2;
        } else {
            --exponent;
        }
    }
    int result = 1;
    while (!stack.isEmpty()) {
        result *= stack.pop() ? result : x;
    }
    return result;
}

所以必须区分：

  • 准备递归参数做什么
  • 如何处理递归调用的部分结果
  • 如何在函数中合并/处理多个递归调用
  • 利用美好的事物，例如x成为最终常数

不难，也许令人费解，所以玩得开心。

于 2018-01-19T10:06:25.440 回答