Authors:
Tony Gaddis
Chapter:
Recursion
Exercise:
Programming Exercises
Question:8 | ISBN:9780132576376 | Edition: 2
Question
Ackermann’s Function is a recursive mathematical algorithm that can be used to test how well a system optimizes its performance of recursion. Design a function ackermann(m, n), which solves Ackermann’s function. Use the following logic in your function:
If m = 0 then return n + 1
If n = 0 then return ackermann(m - 1, 1)
Otherwise, return ackermann(m - 1, ackermann(m, n - 1))
Once you’ve designed your function, test it by calling it with small values for m and n.
Answer
Program code:
def ackermann(m, n):
"""
Recursive function to calculate Ackermann's function.
Arguments:
- m: The first parameter of the Ackermann function.
- n: The second parameter of the Ackermann function.
Returns:
- The result of the Ackermann function for the given m and n.
"""
if m == 0:
# Base case 1: If m is 0, return n + 1.
return n + 1
elif n == 0:
# Base case 2: If n is 0, call ackermann with m - 1 and 1 as arguments.
return ackermann(m - 1, 1)
else:
# Recursive case: Call ackermann with m - 1 and ackermann with m and n - 1 as arguments.
return ackermann(m - 1, ackermann(m, n - 1))
# Test the function with small values of m and n
m = 3
n = 4
result = ackermann(m, n)
print(f"Ackermann({m}, {n}) = {result}")
Executed Output:
Ackermann(3, 4) = 125