Here are some weirder recursive algorithms.

TAK

The Tak function, also known as Takeuchi’s triple recursion, 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]. Here is a version in Lisp [2]:

(defun tak' (x y z)
  (cond ((not (< y x)) z)
        (t (tak' (tak' (1- x) y z)
                 (tak' (1- y) z x)
                 (tak' (1- z) x y)))))

This is one of those non-sensical algorithms that can be used to profile efficiency, either of a system or language, similar to Ackermann. It was used as a means of testing stack instructions, data moving, and arithmetic. The amount of recursion performed by this algorithm is significant, in fact it was described in one books as “a recursive algorithm with cubic explosion” [3]. 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 [4]. 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)
  2. Gabriel, R.P., Performance and Evaluation of Lisp Systems (1985)
  3. Robertson, I.B., “Hope+ on Flagship”, in Proc. Functional Programming, pp.296-307 (1989)
  4. Feinberg, M., “Fibonacci-Tribonacci”, The Fibonacci Quarterly, 1(3), pp.71-74 (1963)