Introduction

• The Ackermann Function is a classic example in theoretical computer science.
• It is total computable (always terminates for non-negative integers) but not primitive recursive.
• It grows faster than any primitive recursive function — even faster than exponential or factorial.
• Named after Wilhelm Ackermann (1928), later simplified by Rózsa Péter.

Why It Matters

• Proves that not all computable functions are primitive recursive.
• Used as a benchmark for recursion depth and stack performance.
• The inverse Ackermann function α(n) appears in Union-Find complexity analysis — it’s effectively constant for all practical inputs.

Definition

Recursive Formula

A(0, n) = n + 1
A(m, 0) = A(m-1, 1)          for m > 0
A(m, n) = A(m-1, A(m, n-1))  for m > 0, n > 0

Value Table

A(m,n)   n=0    n=1    n=2    n=3    n=4
m=0       1      2      3      4      5
m=1       2      3      4      5      6
m=2       3      5      7      9      11
m=3       5      13     29     61     125
m=4      13   65533  2^65536-3  ...   (astronomically large)

• A(4, 2) ≈ 2^65536 — a number with ~20,000 digits.
• A(4, 3) is incomprehensibly large — more digits than atoms in the observable universe.

Pattern by Row

m=0: A(0,n) = n+1                    (successor)
m=1: A(1,n) = n+2                    (addition)
m=2: A(2,n) = 2n+3                   (multiplication-like)
m=3: A(3,n) = 2^(n+3) - 3            (exponentiation-like)
m=4: A(4,n) = tower of 2s of height n+3 - 3  (tetration-like)

C++ Implementation

Basic Recursive

#include <iostream>
 
long long ackermann(long long m, long long n) {
    if (m == 0) return n + 1;
    if (n == 0) return ackermann(m - 1, 1);
    return ackermann(m - 1, ackermann(m, n - 1));
}
 
int main() {
    std::cout << ackermann(0, 0) << "\n"; // 1
    std::cout << ackermann(1, 1) << "\n"; // 3
    std::cout << ackermann(2, 2) << "\n"; // 7
    std::cout << ackermann(3, 3) << "\n"; // 61
    // ackermann(4, 1) — stack overflow for most systems
}

Memoized Version (handles slightly larger inputs)

#include <iostream>
#include <map>
 
std::map<std::pair<long long,long long>, long long> memo;
 
long long ackermann(long long m, long long n) {
    if (m == 0) return n + 1;
 
    auto key = std::make_pair(m, n);
    auto it = memo.find(key);
    if (it != memo.end()) return it->second;
 
    long long result;
    if (n == 0)
        result = ackermann(m - 1, 1);
    else
        result = ackermann(m - 1, ackermann(m, n - 1));
 
    memo[key] = result;
    return result;
}
 
int main() {
    std::cout << ackermann(3, 4) << "\n"; // 125
    std::cout << ackermann(3, 6) << "\n"; // 509
}

Iterative with Explicit Stack (avoids call stack overflow)

#include <iostream>
#include <stack>
 
long long ackermann_iterative(long long m, long long n) {
    std::stack<long long> stk;
    stk.push(m);
 
    while (!stk.empty()) {
        m = stk.top(); stk.pop();
 
        if (m == 0) {
            n = n + 1;
        } else if (n == 0) {
            stk.push(m - 1);
            n = 1;
        } else {
            stk.push(m - 1);
            stk.push(m);
            n = n - 1;
        }
    }
    return n;
}
 
int main() {
    std::cout << ackermann_iterative(3, 4) << "\n"; // 125
    std::cout << ackermann_iterative(3, 7) << "\n"; // 4093
}

Complexity

Time Complexity

• Not expressible in standard Big-O notation.
• Grows faster than any primitive recursive function.
• For small m: manageable. For m ≥ 4: practically infinite.

A(3, n) ≈ O(2^n)       — exponential
A(4, n) ≈ O(2^2^...^2) — tetration (tower of powers)

Space Complexity (Call Stack)

• Recursion depth grows extremely fast.

A(3, 3) → ~500 recursive calls
A(3, 6) → ~10,000+ recursive calls
A(4, 1) → stack overflow on most systems

• Use iterative + explicit stack for deeper computations.

Inverse Ackermann α(n)

• The inverse of the Ackermann function.
• Grows so slowly it’s effectively O(1) for all practical n.
• Appears in Union-Find (Disjoint Set Union) amortized complexity: O(α(n)) per operation.
• For n = 10^80 (atoms in universe), α(n) = 4.

Primitive Recursive vs General Recursive

Property                  Primitive Recursive    Ackermann Function
Always terminates         Yes                    Yes
Bounded loop depth        Yes                    No (unbounded recursion)
Expressible in for-loops  Yes                    No
Growth rate               At most exponential    Faster than any PR function

• Ackermann proves the primitive recursive functions are a strict subset of all computable functions.

Key Takeaways

• A(m, n) always terminates but grows hyper-exponentially.
• Not primitive recursive — cannot be expressed with bounded loops.
• Practical use: inverse Ackermann α(n) in Union-Find complexity.
• For m ≥ 4, values are astronomically large — only small inputs are computable in practice.
• Use an explicit stack to avoid call stack overflow for larger inputs.