A recursive process is one in which objects are defined in terms of other objects of the same type. Using some sort of recurrence relation, the entire class of objects can then be built up from a few initial values and a small number of rules. The Fibonacci numbers are most commonly defined recursively. Care, however, must be taken to avoid self-recursion, in which an object is defined in terms of itself, leading to an infinite nesting.

(Go Up)

Linear Recursion

The simplest form of recursion is linear recursion. It occurs where an action has a simple repetitive structure consisting of some basic step followed by the action again.

Factorial

The factorial function is a popular mathematical example:

f(0) = 1                    --base case
f(n) = n*f(n-1),  if n > 1  --general case

If the base case of the recursion takes time `a' and the recursive step takes time `b' then a linear recursive routine making `n' recursive calls takes time a+b*(n-1) in total; this is O(n). For the factorial function, the number of calls is the value of its parameter.

(Go Up)

Exponentiation

In the case of the following exponentiation function which calculates xⁿ, or x**n, the number of calls is not equal to the parameter n but to its logarithm.

Pre: x > 0
expn(x, 0) = 1
expn(x, n) = 1 / expn(x, -n),      if n < 0
expn(x, n) = (expn(x, n div 2))2,  if n > 0 and n is even
expn(x, n) = n * expn(x, n-1),     if n > 0 and n is odd

Note the precondition, for if x is zero and n is negative then xⁿ implies division by zero. It is fairly easy to see that this routine is correct but we prove it here to illustrate general principles. Firstly we show that the routine terminates for all values of n. If n equals zero it certainly terminates. Otherwise, if n is greater than zero then a recursive call is made with a new parameter n div 2, or with n-1, which are strictly less than the old value of n and still greater than or equal to zero. Therefore the successive values of parameter n remain greater than or equal to zero and are decreasing. Such an integer quantity cannot decrease for ever without reaching zero when the algorithm terminates. Note that a positive real valued quantity can be reduced repeatedly without ever reaching zero so such a proof cannot be based on a real quantity: eg. 1, 1/2, 1/4, 1/8, ... . If n is negative the routine calls itself with a new value, minus n, and subsequently terminates by the above. This exhausts all cases. Secondly, we show that the algorithm calculates the correct result for all n>=0:

If n>0:
  (i)  x-n = 1/xn   if x~=0
 (ii)  x0 = 1
(iii)  x2n = (xn)2
 (iv)  x2n+1 = x*x2n

Finally the time complexity of the routine fits the form for logarithmic complexity:

T0 = b
Tn = Tn/2+a   if n>0

which has solution

Tn = a * log(n) + b + a,   n>=1

Many languages provide a numerical exponentiation operator `**' in which case the above algorithm is not required for numbers. However some languages do not provide this operator as standard. In addition other objects, such as matrices, can also be multiplied and therefore exponentiated. With modification, this algorithm can also be used for the latter purpose.

(Go Up)

Mutual Recursion

In order to check and compile a routine call, a compiler must know the type of the routine, the number of parameters and so on. In direct recursion the routine header which contains this information is seen before any call within the procedure body or later. In mutual recursion the routines must be defined in some order. This means that a call of at least one routine must be compiled before its definition is seen. Different programming languages approach this problem in various ways. Some use separate forward definitions of routine headers to give sufficient information to compile a call and body definitions to contain those calls.

(Go Up)

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

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:

(Go Up)

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)     
 { if( n <= 2 ) return 1;
   else return fib(n-1)+fib(n-2);
 }

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

                       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.

(Go Up)

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); }

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.

(Go Up)

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.

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.

(Go Up)

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.

(Go Up)

Sources

L.A1lison, Dept. of Computer Science UWA 1984,
School of Computer Science & Software Engineering, Monash 1999