Ackermann Function
Problem
The Ackermann function A(m, n) is: A(0, n) = n + 1. A(m, 0) = A(m - 1, 1) when m > 0. A(m, n) = A(m - 1, A(m, n - 1)) when m > 0 and n > 0. Print A(m, n) for the given m and n. It grows very fast, so only small inputs are used.
Constraints
- 0 <= m <= 3
- 0 <= n <= 6
Examples
Input
2 3
Output
9
Solutions
The code is the definition. It makes many calls and goes deep, so inputs stay small (m up to 3). It shows how recursion can be very powerful and very slow.
/*
* Problem : Ackermann.
* Input : m and n.
* Output : A(m, n).
* Approach: Direct recursion.
* Time : exponential
* Space : O(result)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
private static long ack(long m, long n) {
if (m == 0) {
return n + 1;
}
if (n == 0) {
return ack(m - 1, 1);
}
return ack(m - 1, ack(m, n - 1));
}
// This method solves the task. It receives the input and returns the answer.
static long solve(long a, long b) {
// Step 1: Follow the three rules of the definition exactly.
return ack(a, b);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a = scanner.nextLong();
long b = scanner.nextLong();
System.out.println(solve(a, b));
}
}
Hints (2)
- Which rule has the inner call?
- Why is the recursion so deep?