2.2. Recursion

Recursion is when a procedure or function calls itself. It is extremely difficult to grasp at first, but a very powerful concept. Here's a trivial example:

function sum_to_n(n : integer) : integer;
begin
     if n = 1 then sum_to_n := 1
     else sum_to_n := n + sum_to_n(n - 1);
end;

This calculates the sum of the numbers up to n. It works by first finding out the sum of the numbers up to n - 1 and then adding n. This sounds a bit like circular reasoning, and if it wasn't for the first line of the function it would be. The first line prevents the function for endlessly calling itself by explicitly returning the sum of the numbers up to 1, namely 1.

This is the simplest form of recursion, and it would be really easy to replace the whole thing with a loop that goes from 1 to n and increments a counter. Here's a more complex example that would be slightly harder to replace with iteration (although any recursion can be replaced by iteration):

function power(a, b : longint) : longint;
begin
     if b = 0 then power := 1
     else if odd(b) then power := a * power(a, b - 1)
     else power := sqr(power(a, b div 2));
end;

This calculates a^b with order O(log b). It relies on the facts that a^b+1 = a.a^b and a^2b = (a^b)².

Pros of recursion

Recursive procedures are usually much shorter, simpler and easier to debug than iterative versions.
Many algorithms are defined recursively, so it is easy to implement them recursively.
Many data structures are naturally recursive (trees, for example) and so it is natural to operate on them recursively.

Cons of recursion

Recursive procedures are slightly slower than iterative ones, because of the overhead of procedure calls.
Recursive procedures can use a lot of stack space.
Badly thought out recursive procedures can sometimes be very slow. For example, you might be tempted to use the following to calculate any given term of the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13 etc, where each term is the sum of the previous two):
```
function fibonacci(n : integer) : integer;
begin
     if n < 3 then fibonacci := 1
     else fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
end;
```
The problem with this is that fibonacci(n - 1) also calls fibonacci(n - 2), so the latter is calculated twice. For smaller n, the calculation is done even more times. The net result is that the running time is exponential. A far better way to do this would be as follows:
```
function fibonacci(n : integer) : integer;
var
   prev, cur, temp : integer;
   i : integer;
begin
     prev := 0;
     cur := 1;
     for i := 2 to n do
      begin
       temp := prev + cur;
       prev := cur;
       cur := temp;
      end;
     fibonacci := cur;
```
It's longer than the recursive version, but much, much, faster.

Caching

Sometimes it isn't so trivial to convert a recursive algorithm into an iterative one, but you still know that the same work is being done repeatedly and want to eliminate this. A quick way (although not necessarily the best; dynamic programming is usually better) to do this is to save the result the first time it is calculated, and then use the saved version later. This relies on there being enough memory to save all possible results that one might want to store.

Here is an example, applied to the Fibonacci problem.

var
   cache : array[1..MAXN] of longint;

procedure initialise;
begin
     fill cache with -1's, indicating that the value isn't known
     fillchar(cache, sizeof(cache), 255); 
     if we initialise the first 2 here, it simplies the real function
     cache[1] := 1;
     cache[2] := 1;
end;

function fibonacci(n : integer) : longint;
begin
     if (cache[n] = -1) then
       cache[n] := fibonacci(n - 1) + fibonacci(n - 2);
     fibonacci := cache[n];
end;

[Prev] [Next] [Up]

Last updated Sat May 31 19:49:09.0000000000 2008. Copyright Bruce Merry (bmerry '@' gmail dot. com).