Binary Recursion

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

Algorithms
 glossary
 Recursion
  Linear
  Binary
  Permutations
  Partition
  N-Queens
  N-Queens 3D
  Necklaces
  Self-Ref

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: 12345...
mature: 01123...
juvenile: 10112...
total: 11235...

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]

n=[  ], fib(n)=[  ]

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*2n/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 nth Fibonacci number depends on the (n-1)th and (n-2)th numbers. A routine is written to calculate the nth 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
 |fibn+1   fibn|   | 1  1 |
 |             | = |      |
 |fibn   fibn-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)2 + fib(n-1)2
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.

© L.A.,
Department of Computer Science UWA 1984-86, Department of Computer Science Monash 1986, and (HTML) Computer Science & Software Engineering, Monash University 1999
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Tuesday, 21-Oct-2014 14:45:00 EST.