User Tools

Site Tools


cookbook:recursion

McCarthy 91 function

In this section an example of a recursive function is presented. A famous example of recursion is the so called McCarthy 91 function http://en.wikipedia.org/wiki/McCarthy_91_function. This function is defined by:

func mc91(val n: nat) -> nat =
|[ ( n >  100 -> ret n - 10
   | n <= 100 -> ret mc91(mc91(n + 11))
   )
]|

This function returns 91 for all integer arguments n ≤ 101 and returns n − 10 for n > 101. It was conceived by John McCarthy. He invented the programming language Lisp in 1960.

cookbook/recursion.txt · Last modified: Friday, 11 May 2007 : 12:29:32 (external edit)