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

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:

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

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

Thus, T(n)>a*2T(1) = T(2) = a for some constant a T(n) = b + T(n-1)+T(n-2) for some constant b > 2T(n-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:

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.

### 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:

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_{n-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: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]

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