Programming Praxis

John McCarthy’s 91 function is a recursive function designed as a test case for formal verification of computer programs. It is defined as follows:

M(n) = n - 10,     if n > 100
     = M(M(n+11)), if n <= 100

For instance, when n = 87:

M(87)
M(M(98))
M(M(M(109)))
M(M(99))
M(M(M(110)))
M(M(100))
M(M(M(111)))
M(M(101))
M(91)
M(M(102))
M(92)
M(M(103))
M(93)
M(M(104))
M(94)
M(M(105))
M(95)
M(M(106))
M(96)
M(M(107))
M(97)
M(M(108))
M(98)
M(M(109))
M(99)
M(M(110))
M(100)
M(M(111))
M(101)
91

Your task is to write a program that shows the call history of a call to the 91 function in a manner similar to that shown for M(87) above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2