Subj : Re: Are recursive functions ever needed?
To   : comp.programming
From : Richard Heathfield
Date : Sun Oct 02 2005 03:20 am

Tatu Portin said:

> Are recursive functions ever needed

No. They are, however, occasionally desirable.

In mathematics, recursion is commonplace, and is frequently used to define 
functions. For example, n! is defined to be 1 for n = 0, and n * (n-1)! for 
n > 0. But only a newbie programmer would calculate factorials this way in 
a program!

In general, recursive functions are at their best when a problem can be 
thought of as a collection of sub-problems similar in nature to the main 
problem. Consider, for example, the problem of sorting a bunch (that's a 
technical term!) of numbers into order. A bunch is defined as 0 or more 
numbers. A bunch with 0 or 1 numbers in it is considered to be already 
sorted, of course.

Here is a bunch of numbers:

123 46 13 68 21 42 97 615 153 168 12 48 19 132

Rather than tackle the problem of comparing all these numbers to lots of 
other numbers, let's just compare them to one number - the first. We'll 
split the bunch into three new bunches - those less than the first number, 
those equal to it, and those greater than it:

Less: 46 13 68 21 42 97 12 48 19
Equal: 123
Greater: 615 153 168 132

Now that we've done that, we know that 123 is in "the right place", so all 
that remains is to sort the bunch of lesser numbers and the bunch of 
greater numbers. Well, we already have a solution to that problem, so why 
not use it?

46 13 68 21 42 97 12 48 19 is sorted in the same way, then:

Less: 13 21 42 12 19
Equal: 46
Greater: 68 97 48

We now know that 46 is in "the right place". And so on.

The point is that we don't have to do any complicated tracking. All we have 
to do is know how big a bunch we're sorting, which is easy to calculate. 
This algorithm is naturally recursive, and it happens that a recursive 
function deals with it in a pretty efficient and elegant manner.

If a recursive solution is inelegant, don't use it.

If a recursive solution is elegant, however, think twice before using it! 
Some recursive solutions look very neat and tidy, but have hidden traps. 
Consider, for example, this routine:

unsigned long fib(unsigned long n)
{
  return n < 2 ? 1 : fib(n - 1) + fib(n - 2);
}

If you haven't come across it before, the problem is not immediately 
obvious.

But for some applications, recursion is the most natural, elegant, and 
descriptive way to model the problem. Sorting, searching, and parsing are 
the most obvious applications where recursion works well.

-- 
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/2005
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

.