# Weird recursive algorithms

Here are some weirder recursive algorithms.

### TAK

The Tak function was invented by Ikuo Takeuchi of the Electrical Communication Laboratory of Nippon Telephone and Telegraph Co., for the purpose of comparing the speeds of LISP systems . This is one of those non-sensical algorithms that can be used to profile efficiency, either of a system or language, similar to Ackermann. The amount of recursion performed by this algorithm is significant. Here is the algorithm:

tak(x,y,z) = y, if x<=y, otherwise
tak(x,y,z) = tak(tarai(x-1,y,z), tak(y-1,z,x), tak(z-1,x,y))

Call this with tak(10,2,9) returns a calue of 9, calling the function 4145 times. Here is the C version of the function:

```int tak(int x, int y, int z) {
if (x > y)
return tak(tak(x-1,y,z),tak(y-1,z,x),tak(z-1,x,y));
else
return y;
}
```

### Zibonacci

This is a weird rendition of Fibonacci which tends to calculate results which appear to zig and zag.

zib(0) = 1
zib(1) = 1
zib(2) = 2
zib(2n+1) = zib(n) + zib(n-1) + 1, if n>0 (odd values 3 and higher)
zib(2n) = zib(n) + zib(n+1) + 1, if n>1 (even values 4 and higher)

The C program to calculate this looks like:

```int zib(int n) {
if (n == 0)
return 1;
else if (n == 1)
return 1;
else if (n == 2)
return 2;
else if (n%2 == 1 && n >= 3) // odd
return zib((n-1)/2) + zib((n-1)/2-1) + 1;
else if (n%2 == 0 && n >= 4) // even
return zib(n/2) + zib(n/2+1) + 1;
}
```

Here is the output for 1 to 20:

1  2  3  6  4  10  6  11  10  15  11  17  15  18  17  22  18  26  22  27

### Tribonacci

This algorithm mimics Fibonacci, but adds the previous three values instead of two. The first three Tribonacci numbers are 0, 0, 1.

trib(0) = 0
trib(1) = 0
trib(2) = 1
trib(n) = trib(n-1) + trib(n-2) + trib(n-3)

Here are the values 0 to 10: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81

Here is the algorithm written in C:

```int trib(int n) {
if (n == 0 || n == 1)
return 0;
else if (n == 2)
return 1;
else
return trib(n-1) + trib(n-2) + trib(n-3);
}
```

 McCarthy, J., “An interesting LISP function”, ACM Lisp Bulletin, 3, pp.6-8 (1979)

## One thought on “Weird recursive algorithms”

1. Travis says: Looks like Zibonacci isn’t in the OEIS. Maybe you should add it 😉

https://oeis.org/

This site uses Akismet to reduce spam. Learn how your comment data is processed.