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;
     if n = 1 then sum_to_n := 1
     else sum_to_n := n + sum_to_n(n - 1);

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

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

Pros of recursion

Cons of recursion


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.

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

procedure initialise;
     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;

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

[Prev] [Next] [Up]

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