## McCarthy’s 91 Function

### September 20, 2013

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

### 10 Responses to “McCarthy’s 91 Function”

1. Paul said

In Python.

```def m91(n):
level = 1
while level:
print "M(" * level + str(n) + ")" * level
if n > 100:
n -= 10
level -= 1
else:
n += 11
level += 1
print n
```
2. raj said

class rec
{
public int print(int n,int k)
{
for(int i=0;i<k;i++)
System.out.print("M(");
System.out.print(n);
for(int i=0;i100)
return n-10;
else
{
n = print(n+11,k+1);
return print(n,k);
}
}
public static void main(String args[])
{
rec r = new rec();
System.out.println(r.print(87,1));
}
}

3. John said

C++

```#include <iostream>
using namespace std;

int M (int n, int level = 1);

int main()
{
int n = M(87);
cout << n << endl;
return 0;
}

int M (int n, int level) {
for (int i = 0; i < level; i++)
cout << "M(";
cout << n;
for (int i = 0; i < level; i++)
cout << ")";
cout << endl;

if (n > 100)
return n - 10;
else
return M(M(n+11, level+1), level);
}
```
4. Jussi Piitulainen said

``` (define (expand M e)   (if (pair? e) `(M ,(apply expand e))       (if (> e 100) (- e 10) `(M (M ,(+ e 11))))))```

``` ```

```(define (trace n)   (let loop ((e `(M ,n)))     (write e) (newline)     (if (pair? e) (loop (apply expand e))))) ```

5. Graham said

I used this as an excuse to learn about Haskell’s `Writer` monad.

```import Control.Monad.Writer

-- Simple recursive version
m :: Integer -> Integer
m n | n > 100   = n - 10
| otherwise = m . m \$ n + 11

-- Recursive with counter and writer for output
m' :: Integer -> Int -> Writer [String] Integer
m' n c | c <= 0    = do
tell [show n]
return n
| otherwise = do
let crc = concat . replicate c
tell [crc "M(" ++ show n ++ crc ")"]
if n > 100 then
m' (n - 10) (c - 1)
else
m' (n + 11) (c + 1)

-- Example
main :: IO ()
main = mapM_ putStrLn \$ snd \$ runWriter (m' 87 1)
```
6. An interpreter for “M” expressions in SML

```datatype m = I of int | M of m

fun step (M (I n)) = if n > 100 then I (n - 10) else M (M (I (n + 11)))
| step (M x)     = M (step x)
| step (I x)     = I x

fun show x =
let
fun showM (I x) = print (Int.toString x)
| showM (M m) = (print "M("; showM m; print ")")
in
(showM x ; print "\n")
end

fun eval (I x) = x
| eval x     = let val y = step x
in (show y; eval y) end

(*
:- eval (M (I 87));
M(M(98))
M(M(M(109)))
...
M(101)
91
*)
```
7. #include <stdlib.h>
#include <stdio.h>

long mccarthy(long in, int depth)
{
int i;
for (i = 0; i <= depth; ++i) {
printf("M(");
}
printf("%ld", in);
for (i = 0; i <= depth; ++i) {
printf(")");
}
printf("\n");
if (in > 100) {
return in – 10;
} else {
return mccarthy(mccarthy(in + 11, depth+1), depth);
}
}

int main(int argc, char** args)
{
if (argc != 2) return 1;

printf("%ld\n", mccarthy(atoi(args[1]), 0));

return 0;
}

8. ```#include <stdlib.h>
#include <stdio.h>

long mccarthy(long in, int depth)
{
int i;
for (i = 0; i <= depth; ++i) {
printf("M(");
}
printf("%ld", in);
for (i = 0; i <= depth; ++i) {
printf(")");
}
printf("\n");
if (in > 100) {
return in - 10;
} else {
return mccarthy(mccarthy(in + 11, depth+1), depth);
}
}

int main(int argc, char** args)
{
if (argc != 2) return 1;

printf("%ld\n", mccarthy(atoi(args[1]), 0));

return 0;
}
```
9. Juan Ignacio Saba said

My first attempt was to do it recursively:
http://pastebin.com/DxVUhJP5

```#!/usr/bin/perl -w

use strict;
use warnings;

my \$n = <STDIN>;
chomp(\$n);

mprint(\$n, 1);

sub mprint {
my \$n = shift;
my \$level = shift;

print tostring(\$n, \$level)."\n";
return if \$level == 0;

mprint(\$n+11, \$level+1) if \$n <= 100;
mprint(\$n-10, \$level-1) if \$n > 100;
}

sub tostring {
my \$n = shift;
my \$level = shift;

return "\$n" if \$level <= 0;
return "M(\$n)" if \$level == 1;
return "M(".tostring(\$n, \$level-1).")";
}
```

It works pretty well. It does give me the “Deep recursion on subroutine …” warning for numbers below 53, but that’s harmless in this case.

Still, I wanted a clean output and didn’t want to recompile Perl to change the recursion threshold, so here’s the non-recursive implementation:
http://pastebin.com/R5n0eakF

```#!/usr/bin/perl -w

use strict;
use warnings;

my \$n = <STDIN>;
chomp(\$n);

mprint(\$n, 1);

sub mprint {
my \$n = shift;
my \$level = shift;

while(\$level > 0) {
print tostring(\$n, \$level)."\n";
if(\$n <= 100) { \$n += 11; \$level++; }
else { \$n -= 10; \$level--; }
}

print tostring(\$n, \$level)."\n";
}

sub tostring {
my \$n = shift;
my \$level = shift;

return "\$n" if \$level <= 0;
return "M(\$n)" if \$level == 1;
return "M(".tostring(\$n, \$level-1).")";
}
```

I did leave the tostring implementation recursive. I guess I like recursion :).

10. Juan Ignacio Saba said

Ha! actually, it still gives me deep recursion warning for numbers below -977, but that’s now because of the tostring funcion :).