## McCarthy’s 91 Function

### September 20, 2013

First, a simple version that just computes the value of the function:

```(define (m n)   (if (< 100 n) (- n 10)     (m (m (+ n 11)))))```

To show all the recursive steps requires that we track the depth of the recursion:

```(define (mccarthy n)   (define (m n d)     (do ((i 0 (+ i 1))) ((= i d) (display n))       (display "M("))     (do ((i 0 (+ i 1))) ((= i d) (newline))       (display ")"))     (if (positive? d)         (if (< 100 n)             (m (- n 10) (- d 1))             (m (+ n 11) (+ d 1)))))   (m n 1))```

Example output for `(mccarthy 87)` was shown on the first page. If you want to have some fun, try `(mccarthy -3)`. You can run the program at http://programmingpraxis.codepad.org/BKsY6oeS.

Pages: 1 2

### 8 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;
}
```