A binary-recursive routine (potentially) calls itself twice. The Fibonacci numbers are the sequence:
The Fibonacci sequence is usually defined as follows:
There are two base cases. The recursive step uses fib twice. This leads directly to a binary-recursive coding:fib(1) = fib(2) = 1 fib(n) = fib(n-1)+fib(n-2), if n>2
This program is clearly correct. It is also unnecessarily slow. Let the time it takes to compute fib(n) be T(n).
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: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)
Plainly a lot of work is being done repeatedly many times. The cure in this case is to write a linear-recursive routine.fib(9) . . . . . . fib(8) fib(7) . . . . . . . . fib(7) fib(6) fib(6) fib(5) . . fib(6) fib(5) ...etc... ... Tree of Calls.
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.
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:
It can be proven by induction. By definition, it holds when n=1. If it holds for a given n then multiplying both sides byn |fibn+1 fibn| | 1 1 | | | = | | |fibn fibn-1| | 1 0 |
show the equation to hold for n+1. Thus the equation holds for all n>=1.| 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):
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: 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, andfib(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
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.
Many operations, such as traversals, on binary trees are naturally binary recursive, like the trees
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.
Department of Computer Science UWA 1984-86, Department of Computer Science Monash 1986, and (HTML) Computer Science & Software Engineering, Monash University 1999