Springboard to functions beyond recursive primitive? Implementation for the Ackermann Peter function

When exploring the springboard technique, I initially used it in simpler situations, with just one recursion – probably a proper subset of primitive recursive functions. However, the need arose to perform an extremely long calculation at work. My first idea was the busy beaver function, but, in addition to its high computational complexity, I was not familiar enough. I then opted for a better-known function: the Ackermann-Peter function.

The Ackermann-Peter Function

This is an easy-to-understand function that takes two integer arguments as input:

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));
}

For more details, see the Wikipedia page or WolframAlpha.

Using the Function

When testing ackermannPeter(3, 3), the result was calculated correctly. However, when executing ackermannPeter(4, 3), a stack explosion occurred. The depth of recursive calls to the Ackermann-Peter function is very large; simply changing the first argument from 3 to 4 made the output, which was 61, become $2^{2^{65536}} - 3$.

Overcoming Stack Limit

The problem lies in the intense recursion of the Ackermann-Peter function, which quickly exhausts the stack. The solution is to use continuations to avoid overloading the stack, implementing the springboard idea.

A step on the trampoline needs three behaviors:

• Indicate whether computation is over.
• Return the calculated value.
• Execute one step and get the next continuation.

For our case (integer return):

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

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

The trampoline itself:

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

Applying to the Ackermann-Peter function: the function is divided into three cases: base case, simple recursion and double recursion. The springboard should control the result of the second recursion. To do this, the second argument becomes a Continuation. If n is already finished, the process continues normally; otherwise, a step is taken in the continuation, generating a new one.

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)
        )))
    );
}

Adding Memoization

Memoization improves performance. Two situations: 1) the result is already in memory; 2) the next step allows you to infer the current result. Memoization is applied after resolving the continuation of the second argument. The implementation with memoization using a HashMap and a long key (combining m and n) is presented, demonstrating a significant reduction in the number of recursive calls. The final version removes the global memory dependency, passing HashMap as an argument.

The above is the detailed content of Springboard to functions beyond recursive primitive? Implementation for the Ackermann Peter function. For more information, please follow other related articles on the PHP Chinese website!