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