超越递归原语的函数的跳板？阿克曼彼得函数的实现

在探索跳板技术时，我最初在更简单的情况下使用它，只有一次递归——可能是原始递归函数的适当子集。 然而，在工作中需要执行非常长的计算。 我的第一个想法是 busy beaver 函数，但是，除了计算复杂度高之外，我还不够熟悉。 然后我选择了一个更知名的函数：Ackermann-Peter 函数。

阿克曼-彼得函数

这是一个易于理解的函数，它接受两个整数参数作为输入：

int ackermannPeter(int m, int n) {
    if (m == 0) {
        return n + 1;
    } else if (n == 0) {
        return ackermannPeter(m - 1, 1);
    }
    return ackermannPeter(m - 1, ackermannPeter(m, n - 1));
}

有关更多详细信息，请参阅维基百科页面或 WolframAlpha。

使用功能

测试ackermannPeter(3, 3)时，结果计算正确。 然而，在执行ackermannPeter(4, 3)时，发生了堆栈爆炸。 Ackermann-Peter函数的递归调用深度非常大；只需将第一个参数从 3 更改为 4，输出 61 就会变成 $2^{2^{65536}} - 3$。

克服堆栈限制

问题在于Ackermann-Peter函数的强烈递归，很快耗尽了堆栈。 解决方案是使用延续来避免堆栈过载，实现跳板思想。

在蹦床上迈出一步需要三种行为：

• 指示计算是否结束。
• 返回计算值。
• 执行一个步骤并获取下一个延续。

对于我们的案例（整数返回）：

interface Continuation {
    boolean finished();
    int value();
    Continuation step();

    static Continuation found(int v) { /* ... */ }
    static Continuation goon(Supplier<Continuation> nextStep) { /* ... */ }
}

蹦床本身：

static int compute(Continuation c) {
    while (!c.finished()) {
        c = c.step();
    }
    return c.value();
}

应用于Ackermann-Peter函数：该函数分为三种情况：基本情况、简单递归和双重递归。 跳板应该控制第二次递归的结果。 为此，第二个参数变为 Continuation。如果n已经完成，则该过程正常继续；否则，在延续中采取一步，生成一个新的。

private static Continuation ackermannPeter(int m, Continuation c) {
    if (!c.finished()) {
        return Continuation.goon(() -> {
            final var next = c.step();
            return Continuation.goon(() -> ackermannPeter(m, next));
        });
    }
    int n = c.value();
    if (m == 0) {
        return Continuation.found(n + 1);
    } else if (n == 0) {
        return Continuation.goon(() -> ackermannPeter(m - 1, Continuation.found(1)));
    }
    return Continuation.goon(() ->
        ackermannPeter(m - 1,
            Continuation.goon(() -> ackermannPeter(m, Continuation.found(n - 1)
        )))
    );
}

添加记忆

记忆可以提高性能。 两种情况：1）结果已经在内存中； 2) 下一步允许您推断当前结果。 在解决第二个参数的延续之后应用记忆化。 提出了使用 HashMap 和 long 键（组合 m 和 n）进行记忆的实现，证明了递归调用数量的显着减少。 最终版本删除了全局内存依赖，并传递 HashMap 作为参数。

以上是超越递归原语的函数的跳板？阿克曼彼得函数的实现的详细内容。更多信息请关注PHP中文网其他相关文章！