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, ... .

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

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)

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

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]

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
 |fibn+1   fibn|   | 1  1 |
 |             | = |      |
 |fibn   fibn-1|   | 1  0 |

 | 1  1 |
 |      |
 | 1  0 |

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)2 + fib(n-1)2

[C/Recn/fibLog.c]

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.