ackerman_iterative.java

import java.util.Arrays;

/**
 * This is the main class for demonstrating the Ackerman function both
 * recursively and iteratively.
 *
 * The Ackerman function is a well-known example of a recursive function that is
 * not primitive recursive.
 *
 * The main method runs a nested loop to compute and prlong the Ackerman function
 * values for a range of inputs.
 *
 * Methods:
 * - main(String[] args): The entry polong of the program. It runs a nested loop
 * to compute and prlong the Ackerman function values.
 * - Ackerman(int i, long n): Computes the Ackerman function recursively.
 * - AckermanIter(int i, long n): Computes the Ackerman function iteratively.
 *
 * @see <a href="https://en.wikipedia.org/wiki/Ackermann_function">Ackermann function</a>
 * @author pakuula@github.com
 * @version 1.0
 * @since 2024-12-12
 */
public class Main {
    /**
     * Computes the Ackermann function iteratively.
     *
     * The Ackermann function is a well-known example of a recursive function that
     * is not primitive recursive.
     * This implementation uses an iterative approach to compute the function.
     *
     * The algorithm uses two arrays, each are of size i+1. The number of loops is
     * i*A(i,n).
     *
     * The algorithm is based on Jerrold W. Grossman and R.Suzanne Zeitman "An
     * inherently iterative computation of ackermann's function".
     *
     * @see <a href="https://doi.org/10.1016%2F0304-3975%2888%2990046-1">An
     *      inherently iterative computation of ackermann's function (1988)</a>
     * @param i the first parameter of the Ackermann function.
     * @param n the second parameter of the Ackermann function.
     * @return the result of the Ackermann function for the given parameters.
     */
    public static long AckermanIter(int i, long n) {
        var vals = new long[i + 1];
        Arrays.fill(vals, 0);
        var goal = new long[i + 1];
        Arrays.fill(goal, 1);
        goal[i] = -1;

        while (true) {
            var value = vals[0] + 1;
            for (int j = 0; j < i + 1; j++) {
                var v = vals[j];
                vals[j] += 1;
                if (v == goal[j]) {
                    goal[j] = value;
                } else {
                    break;
                }
            }
            if (vals[i] == n + 1) {
                return value;
            }
        }
    }

    /**
     * Computes the Ackermann function, a well-known example of a recursive function
     * that is not primitive recursive.
     *
     * @param i the first parameter, a non-negative longeger
     * @param n the second parameter, a non-negative longeger
     * @return the result of the Ackermann function for the given parameters
     */
    public static long Ackerman(int i, long n) {
        if (i == 0) {
            return n + 1;
        }
        if (n == 0) {
            return Ackerman(i - 1, 1);
        }
        return Ackerman(i - 1, Ackerman(i, n - 1));
    }


    public static void main(String[] args) {
        for (int i = 0; i < 4; i++) {
            for (long n = 0; n < 5; n++) {
                System.out.println("(" + i + ", " + n + "): Recursive " + Ackerman(i, n) +
                        ",\tIterative " + AckermanIter(i, n));

            }
        }
    }
}