Binary Recursion

A binary-recursive routine (potentially) calls itself twice. The Fibonacci numbers are the sequence:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... .

Each number is the sum of the two previous numbers. Fibonacci devised the series, in 1202, to plot the population explosion of rabbits. A pair of (abstract) rabbits become fertile at the age of one month, can produce a new pair of offspring each month, and never die:

month:	1	2	3	4	5	...
mature:	0	1	1	2	3	...
juvenile:	1	0	1	1	2	...
total:	1	1	2	3	5	...

Fibonacci

The Fibonacci sequence is usually defined as follows:

fib(1) = fib(2) = 1
fib(n) = fib(n-1)+fib(n-2),  if n>2

There are two base cases. The recursive step uses fib twice. This leads directly to a binary-recursive coding:


function fib(n)     // JavaScript
 { if( n <= 2 ) return 1;
   else return fib(n-1)+fib(n-2);
 }

[C/Recn/fibBin.c]

This program is clearly correct. It is also unnecessarily slow. Let the time it takes to compute fib(n) be T(n).

T(1) = T(2) = a            for some constant a
T(n) = b + T(n-1)+T(n-2)   for some constant b
     > 2T(n-2)

Thus, T(n)>a*2^n/2. The time taken grows exponentially with n. The reason is that fib(9), for example, calls fib(8) and fib(7). Fib(8) calls fib(7) again and fib(6). The trace of calls can be viewed pictorially:

                       fib(9)
                      .      .
                    .          .
                  .              .
             fib(8)               fib(7)
            .      .             .      .
           .        .           .        .
       fib(7)      fib(6)   fib(6)      fib(5)
      .      .
 fib(6)     fib(5)     ...etc...
    ...
Tree of Calls.

Plainly a lot of work is being done repeatedly many times. The cure in this case is to write a linear-recursive routine.

Faster

The n^th Fibonacci number depends on the (n-1)^th and (n-2)^th numbers. A routine is written to calculate the n^th and the (n-1)^th numbers from the (n-1)^th and (n-2)^th numbers. This forms the basis of a simple linear-recursion.


function f(a, b, n)
 { if(n <= 1) return b;
   else return f(b, a+b, n-1);
 }

function fib(n)
 { return f(0, 1, n); }

[C/Recn/fibRec.c]

Note the two parameters a and b which hold two successive Fibonacci numbers. This linear recursive version takes O(n) time. There is also an iterative version of this example.

Fastest?

With a little careful thought the previous algorithm is reasonably easy to discover but the following one as altogether more cunning. Defining fib(0)=0, the following matrix equation can be seen to hold:

                       n
 |fib_n+1   fib_n|   | 1  1 |
 |         | = |      |
 |fib_n   fib_n-1|   | 1  0 |

It can be proven by induction. By definition, it holds when n=1. If it holds for a given n then multiplying both sides by

 | 1  1 |
 |      |
 | 1  0 |

show the equation to hold for n+1. Thus the equation holds for all n>=1.

Now the technique of the exponentiation routine that was given earlier can be applied. By squaring the matrix on the left-hand side, expressions can be found for fib(2n) and fib(2n-1) in terms of fib(n) and fib(n-1):

fib(2n) = fib(n+1)*fib(n) + fib(n)*fib(n-1)
        = fib(n)*(fib(n+1)+fib(n-1))
        = fib(n)*(fib(n)+2*fib(n-1))

fib(2n-1) = fib(n)² + fib(n-1)²

This means that if n is even, fib(n) and fib(n-1) can be found in one step from fib(n div 2) and fib(n div 2-1). If n is odd then n-1 is even and we can find fib(n-1) and fib(n-2) in the same way and from them fib(n). In either case fib(n) and fib(n-1) can be found in one step from fib(n div 2) and fib(n div 2-1). Using this repeatedly, fib(n) can be found in O(log(n)) time:


[C/Recn/fibLog.c]

See F. J. Urbanek, and also D. Gries & G. Levin in Information Processing Letters, 11(2), Oct. 1980, pp.66-67 and pp.68-69 respectively, and J. C. P. Miller & D. J. Spencer Brown Computer J., 9, pp.188-190, 1966.) This gives an O(log(n)) time Fibonacci routine. There is also an iterative version of this example.

The magnitude of the improvement from an exponential-time routine to a logarithmic-time routine cannot be overstated. The moral of the Fibonacci numbers is not that binary-recursion is bad, rather that the programmer should be well aware of what she or he has programmed. Do not stop when you have a working program; there may be a much better one! Instances of binary-recursion in particular should be inspected carefully to ensure that they are necessary. Sometimes they are; operations on binary-recursive data types are often binary-recursive themselves of necessity. See the chapter on trees for examples.

Binary Trees.

Many operations, such as traversals, on binary trees are naturally binary recursive, like the trees

datatype tree e = empty | fork e (tree e) (tree e)

prefix empty = do nothing
prefix (fork e left right)
   = process e; prefix left; prefix right

infix empty = do nothing
infix (fork e left right)
   = infix left; process e; infix right

postfix empty = do nothing
postfix (fork e left right)
   = postfix left; postfix right; process e

There are iterative, non-recursive versions of these binary recursive operations, but it is necessary for the programmer to use an explicit stack data-structure.

Notes

D. E. Knuth, Fundamental Algorithms, The Art of Computer Programming Volume 1, Addison Wesley, 1969, page 78, discusses the Fibonacci series and its history.
[Stirling's approximation] can be used to calculate N!, or usually its log, quickly (and approximately) for large values of N.