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 [1]. 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);
}

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

 

 

One thought on “Weird recursive algorithms

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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