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

Trampolim para funções além do primitivo recursivo? Implementação para a função de Ackermann Peter

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 26553632^{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!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
How does the JVM manage garbage collection across different platforms?How does the JVM manage garbage collection across different platforms?Apr 28, 2025 am 12:23 AM

JVMmanagesgarbagecollectionacrossplatformseffectivelybyusingagenerationalapproachandadaptingtoOSandhardwaredifferences.ItemploysvariouscollectorslikeSerial,Parallel,CMS,andG1,eachsuitedfordifferentscenarios.Performancecanbetunedwithflagslike-XX:NewRa

Why can Java code run on different operating systems without modification?Why can Java code run on different operating systems without modification?Apr 28, 2025 am 12:14 AM

Java code can run on different operating systems without modification, because Java's "write once, run everywhere" philosophy is implemented by Java virtual machine (JVM). As the intermediary between the compiled Java bytecode and the operating system, the JVM translates the bytecode into specific machine instructions to ensure that the program can run independently on any platform with JVM installed.

Describe the process of compiling and executing a Java program, highlighting platform independence.Describe the process of compiling and executing a Java program, highlighting platform independence.Apr 28, 2025 am 12:08 AM

The compilation and execution of Java programs achieve platform independence through bytecode and JVM. 1) Write Java source code and compile it into bytecode. 2) Use JVM to execute bytecode on any platform to ensure the code runs across platforms.

How does the underlying hardware architecture affect Java's performance?How does the underlying hardware architecture affect Java's performance?Apr 28, 2025 am 12:05 AM

Java performance is closely related to hardware architecture, and understanding this relationship can significantly improve programming capabilities. 1) The JVM converts Java bytecode into machine instructions through JIT compilation, which is affected by the CPU architecture. 2) Memory management and garbage collection are affected by RAM and memory bus speed. 3) Cache and branch prediction optimize Java code execution. 4) Multi-threading and parallel processing improve performance on multi-core systems.

Explain why native libraries can break Java's platform independence.Explain why native libraries can break Java's platform independence.Apr 28, 2025 am 12:02 AM

Using native libraries will destroy Java's platform independence, because these libraries need to be compiled separately for each operating system. 1) The native library interacts with Java through JNI, providing functions that cannot be directly implemented by Java. 2) Using native libraries increases project complexity and requires managing library files for different platforms. 3) Although native libraries can improve performance, they should be used with caution and conducted cross-platform testing.

How does the JVM handle differences in operating system APIs?How does the JVM handle differences in operating system APIs?Apr 27, 2025 am 12:18 AM

JVM handles operating system API differences through JavaNativeInterface (JNI) and Java standard library: 1. JNI allows Java code to call local code and directly interact with the operating system API. 2. The Java standard library provides a unified API, which is internally mapped to different operating system APIs to ensure that the code runs across platforms.

How does the modularity introduced in Java 9 impact platform independence?How does the modularity introduced in Java 9 impact platform independence?Apr 27, 2025 am 12:15 AM

modularitydoesnotdirectlyaffectJava'splatformindependence.Java'splatformindependenceismaintainedbytheJVM,butmodularityinfluencesapplicationstructureandmanagement,indirectlyimpactingplatformindependence.1)Deploymentanddistributionbecomemoreefficientwi

What is bytecode, and how does it relate to Java's platform independence?What is bytecode, and how does it relate to Java's platform independence?Apr 27, 2025 am 12:06 AM

BytecodeinJavaistheintermediaterepresentationthatenablesplatformindependence.1)Javacodeiscompiledintobytecodestoredin.classfiles.2)TheJVMinterpretsorcompilesthisbytecodeintomachinecodeatruntime,allowingthesamebytecodetorunonanydevicewithaJVM,thusfulf

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)