ITPEC FE Morning October 2021 Question 9

91 — evaluate the inner call first: it pushes the argument above 100, and the outer call brings it back one higher each time until it reaches 101.

• •M(97) = M(M(108)) = M(98)
• •M(98) = M(M(109)) = M(99)
• •M(99) = M(M(110)) = M(100)
• •M(100) = M(M(111)) = M(101)
• •M(101) = 101 − 10 = 91

Each line uses M(n + 11) = n + 1, valid because n + 11 > 100, so every call from M(97) on equals M(101) = 91. This is McCarthy's 91 function: it returns 91 for every n ≤ 100.

Answer (c)

Why not others:

• •(a) 81, (b) 86 and (d) 96 — each is n − 10 for an argument of 91, 96 or 106, but none of these is the argument that returns: the outer call receives the inner result (98, 99, 100, then 101) and returns only at the first argument above 100, which is 101

Key rule: In nested recursion, evaluate the innermost call, substitute its value, and keep expanding until an argument reaches the base case.

Algorithm and Programming · AI-written, may contain errors