Binary Recursion 

A binaryrecursive routine (potentially) calls itself twice. The Fibonacci numbers are the sequence:
FibonacciThe Fibonacci sequence is usually defined as follows: There are two base cases. The recursive step uses fib twice. This leads directly to a binaryrecursive coding:fib(1) = fib(2) = 1 fib(n) = fib(n1)+fib(n2), 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*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:T(1) = T(2) = a for some constant a T(n) = b + T(n1)+T(n2) for some constant b > 2T(n2) Plainly a lot of work is being done repeatedly many times. The cure in this case is to write a linearrecursive routine.fib(9) . . . . . . fib(8) fib(7) . . . . . . . . fib(7) fib(6) fib(6) fib(5) . . fib(6) fib(5) ...etc... ... Tree of Calls. FasterThe n^{th} Fibonacci number depends on the (n1)^{th} and (n2)^{th} numbers. A routine is written to calculate the n^{th} and the (n1)^{th} numbers from the (n1)^{th} and (n2)^{th} numbers. This forms the basis of a simple linearrecursion.
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: 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_{ } _{ } n fib_{n+1} fib_{n}  1 1   _{ } _{ } =   fib_{n} fib_{n1}  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 lefthand side, expressions can be found for fib(2n) and fib(2n1) in terms of fib(n) and fib(n1): This means that if n is even, fib(n) and fib(n1) can be found in one step from fib(n div 2) and fib(n div 21). If n is odd then n1 is even and we can find fib(n1) and fib(n2) in the same way and from them fib(n). In either case fib(n) and fib(n1) can be found in one step from fib(n div 2) and fib(n div 21). 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.6667 and pp.6869 respectively, andfib(2n) = fib(n+1)*fib(n) + fib(n)*fib(n1) = fib(n)*(fib(n+1)+fib(n1)) = fib(n)*(fib(n)+2*fib(n1)) fib(2n1) = fib(n)^{2} + fib(n1)^{2} The magnitude of the improvement from an exponentialtime routine to a logarithmictime routine cannot be overstated. The moral of the Fibonacci numbers is not that binaryrecursion 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 binaryrecursion in particular should be inspected carefully to ensure that they are necessary. Sometimes they are; operations on binaryrecursive data types are often binaryrecursive 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
There are iterative, nonrecursive versions of these binary recursive operations, but it is necessary for the programmer to use an explicit stack datastructure. Notes
© L.A., Department of Computer Science UWA 198486, Department of Computer Science Monash 1986, and (HTML) Computer Science & Software Engineering, Monash University 1999 

