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

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

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

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;

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