On Wed, 04 Aug 2004 08:59:12 -0400, steve_f <(E-Mail Removed)> wrote:

> I could never really wrap my mind around the concept

> of recursive functions. I'm not sure if this is the right

> place to ask...but if anyone can at least clue me in a

> bit, I would really appreciate it.
A more general programming group might be better...

A recursive function is a function which calls itself. To prevent

inifinite recursion there needs to be at least one case in which

the function doesn't call itself (often called the base case).

Generally the function solves some part of the problem and calls

itself in order to solve the smaller problem that remains. At some

point the smaller problem is so small that the answer is known.

For example here is a non-recursive function to count the number of

strings with the value 'needle' in an array of strings:

sub count_em {

my $count = 0;

for my $item (@_) {

$count++ if $item eq 'needle';

}

return $count;

}

It simply looks at each element in the array (@_) and increments the count

if it is 'needle'.

This could also be done recursively.

An obvious base case is the empty array that cleary contains 0 occurances

of the string "needle".

So just the base case would be:

return 0 if @_ == 0;

For a larger array we can can split it in two, the first element and the

rest of the array. If the first element is "needle" then the answer is

1 + <the number of occurances of "needle" in the rest of the array>, or

just <the number of occurances of "needle" in the rest of the array> if

the first element isn't "needle", in other words:

sub count_em_recursive {

return 0 if @_ == 0; # the base case

my $item = shift @_; # solve part of the problem

my $needle;

if ($item eq 'needle') {

$needle = 1;

} else {

$needle = 0;

}

return $needle + count_em_recursive(@_); # recurse on smaller problem

}

Obviously, this is a remarkably silly thing to do recursively (when

using perl anyway). But examples often suffer from that problem.

Recursion is something a lot of people (in my experience of teaching

anyway) have trouble understanding. It is also one of those things that

seems to "click", and then the person understands...

It's just like "proof by induction" in maths - if you happen to have

done that...

Recursion is usually used with recursive data structures (such as trees) since

a recursive function "maps" easily onto the data structure.

[*]- yes I realise shift operates on @_ by default (in that context), and that

this is actually a place where the &func; syntax is useful

- but I

suspect it would detract from the example...

--

Sam Holden