238. A Function That Grows Too Fast
Challenge1000 ms256 MBSolved by 0%
The Ackermann function is defined as:
A(0, n) = n + 1
A(m, 0) = A(m - 1, 1)
A(m, n) = A(m - 1, A(m, n - 1))
Print A(m, n).
Read the third line carefully: the second argument of the outer call is itself a recursive call. That nesting is why this function cannot be rewritten as a simple loop, and it is the classic example of a function that is computable but not primitive recursive.
It also grows absurdly fast. A(4, 2) has 19,729 digits, so the constraints
here are tiny on purpose.
Constraints - `0 ≤ m ≤ 3` - `0 ≤ n ≤ 6`
Input
A single line containing two integers m and n.
Output
Print one integer, the value of A(m, n).
Input0 0
Output1
Noteis the simplest base case
Input1 1
Output3
Noteis the smallest case using the nested rule
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.