Consider the following recursive function in two non-negative integer arguments
ID: 3639682 • Letter: C
Question
Consider the following recursive function in two non-negative integer arguments m, n.unsigned int A ( unsigned int m , unsigned int n ){if (m == 0) return n+1;if (n == 0) return A(m-1,1);return A(m-1,A(m,n-1));}Denote by A(m, n) the value returned by this function. A(m, n) is called the Ackermann function. We haveA(0, n) = n + 1 for all n > 0. Moreover,A(1, n) = A(0,A(1, n 1)) = 1 + A(1, n 1) = 1 + [1 + A(1, n 2)] = 2 + A(1, n 2)= · · · = n + A(1, 0) = n + A(0, 1) = n + 2 for all n > 0.Derive closed-form mathematical formulas (as functions of n) for the following special cases. Show thedetails of your derivations.
Explanation / Answer
(a) A(2, n) = A(1,A(2, n - 1)) [by the recursive definition of A(m, n)] = 2 + A(2, n - 1) [using the formula for A(1, n)] = 2 + [2 + A(2, n - 2)] [repeating the last two steps] = 2 × 2 + A(2, n - 2) = · · · = 2n + A(2, 0) = 2n + A(1, 1) [by the recursive definition of A(m, 0)] = 2n + 3 [using the formula for A(1, n)]. (b) A(3, n) = A(2,A(3, n - 1)) [by the recursive definition of A(m, n)] (5) = 2A(3, n - 1) + 3 [using the formula for A(2, n)] = 2[2A(3, n - 2) + 3] + 3 [repeating the last two steps] = 22A(3, n - 2) + (2 + 1) × 3 = 23A(3, n - 3) + (22 + 2 + 1) × 3 = · · · = 2nA(3, 0) + (2n-1 + · · · + 22 + 2 + 1) × 3 = 2nA(2, 1) + (2n - 1) × 3 [by the recursive definition of A(m, 0)] = 2n × 5 + (2n - 1) × 3 [using the formula for A(2, n)] = 2n+3 - 3.