Velocity Reviews > Perl > recursive functions

# recursive functions

steve_f
Guest
Posts: n/a

 08-04-2004
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.

Sam Holden
Guest
Posts: n/a

 08-04-2004
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

steve_f
Guest
Posts: n/a

 08-04-2004
OK thanks, now I have two working examples. I took a year of calculus,
but don't think I ever encountered "proof by induction".

This concept has never really clicked for me. For example, I wouldn't
recognize what type of problem would need a recursive solution.

I know the concept is a function calls itself repeatedly until it
runs out and now that there is a base case.

example one:
#!/usr/bin/perl -w
@array = qw( test_1 test_2 test_3 );
print count_em_recursive(@array);
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
}

example two:
#!/usr/bin/perl -w
\$string = "test_1\ntest_2\ntest_3";
print combine(\$string);
sub combine {
my @words = split /\n/, shift;
return @words unless @_;
my @combinations;
for my \$word (@words) {
push @combinations => map { "\$word \$_" } combine(@_);
}
@combinations;
}

Richard Gration
Guest
Posts: n/a

 08-04-2004
In article <(E-Mail Removed)>, "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.

The absolute classic example of a recursive algorithm is the factorial
function. This relies on the relationship

n! = n * (n-1)!

and the fact that

1! = 1

so the code pretty much writes itself ...

#!/usr/bin/perl

my \$f = shift;
print "\$f! = ",factorial(\$f),"\n";

sub factorial {
my \$n = shift;

if (\$n == 1) {
# base case
return 1;
} else {
return \$n * factorial(\$n-1);
}
}

HTH
Rich

Abhinav
Guest
Posts: n/a

 08-04-2004
steve_f wrote:
> OK thanks, now I have two working examples. I took a year of calculus,
> but don't think I ever encountered "proof by induction".
>
> This concept has never really clicked for me. For example, I wouldn't
> recognize what type of problem would need a recursive solution.
>

Some other examples which might help visualize the idea would be

1. Binary Search
2. Factorial
3. Tower of Hanoi problem
4. Directory search of a file system
5. Depth First Search (DFS) of a (binary) tree

I have not mentioned fibonacci series in the list, because that *generally*
would be harder to visualize with the recursive routine ..

HTH

Regards

--

Abhinav

Anno Siegel
Guest
Posts: n/a

 08-04-2004
steve_f <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> OK thanks, now I have two working examples. I took a year of calculus,
> but don't think I ever encountered "proof by induction".

Sounds unlikely. There are lots of propositions in elementary calculus
that are best proved inductively. Also, induction is so important in
all branches of mathematics that teachers tend to bring it up in any
elementary course.

> This concept has never really clicked for me. For example, I wouldn't
> recognize what type of problem would need a recursive solution.

If you have a problem that can't be solved immediately, one technique
to find a solution is often called "Divide and Conquer". That means,
split the problem into two or more sub-problems, so that a solution
of the whole problem can be constructed when the subproblems are solved.
The hope is that the sub-problems will be easier. The technique can
then repeatedly be applied to the sub-problems, simplifying at each
step until all remaining (sub-)problems are immediately solvable.

It may happen that one or more subproblems have the same structure
as the original problem. The subproblems may still be simpler than
the original, for instance by having to deal with smaller numbers
or fewer things.

If that happens, it is an invitation to try a recursive solution.
The advantage is that the sub-problem, having the same structure as
the original, can again be split into sub-problems using the same
technique again, until elementary cases are reached. If the sub-problems
are unrelated to the original, new methods must be found at each level.

> I know the concept is a function calls itself repeatedly until it
> runs out and now that there is a base case.

Strictly speaking, this is slightly too narrow. A function doesn't
have to call itself to be recursive, it may call another function
which calls another which, eventually, calls the first function again.
Technically, a call to a function is recursive if another call to the
same function hasn't returned yet.

[examples snipped]

Anno

Anno Siegel
Guest
Posts: n/a

 08-04-2004
Abhinav <(E-Mail Removed)> wrote in comp.lang.perl.misc:

[recursion]

> Some other examples which might help visualize the idea would be
>
> 1. Binary Search
> 2. Factorial
> 3. Tower of Hanoi problem
> 4. Directory search of a file system
> 5. Depth First Search (DFS) of a (binary) tree

These are good examples, with exception of number 2, which is only popular.
I have never quite understood why.

Nothing in multiplying the first few numbers together particularly invites
recursion, not any more than adding them up would. Calculating the number
of permutations of n things (which happens to be n!) *is* a naturally
recursive problem. Calculating factorials isn't.

Anno

Anno Siegel
Guest
Posts: n/a

 08-04-2004
Richard Gration <(E-Mail Removed)> wrote in comp.lang.perl.misc:
> In article <(E-Mail Removed)>, "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.

>
> The absolute classic example of a recursive algorithm is the factorial
> function. ...

Classic only in the sense of mythology. Nothing about the factorial
invites a recursive algorithm, and the recursive implementation has
no advantages over an iterative one.

Anno

steve_f
Guest
Posts: n/a

 08-04-2004
wow....I kind of wrote my own recursive function...
well, I rewrote it from an example in some other
language...

#!c:\perl\bin\perl.exe -w

\$m = 5;
\$n = 10;

print multiply_em(\$m, \$n);

sub multiply_em {
my (\$m, \$n) = @_;
if (\$n == 1) {
return \$m;
}
return \$m + multiply_em(\$m, \$n - 1);
}

thanks everyone...it is begining to become clear to me.
yes, my calculus was so long ago, but I think that is what
makes perl attractive to me.

ok...I think the trick is in the \$n-1 ...so it is counting down as
it is passing through the function almost like a for construction
for x = 0, x < 10, x++

here's the other list of examples:
compute the power of x to the n, where x and n are both integers
print the characters of a string in reverse order
sum the numbers of an array of doubles
print the items of a linked list, assuming a toString()method is defined for the item part of a Node
find the minumum value in an array of ints
sort an array using the strategy of the selection sort
search through a sorted arrya using the strategy of the binary search

hmmmm....!! ok, yes this post was off topic, I really should of found a
programming group!

steve_f
Guest
Posts: n/a

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

>sub multiply_em {
> my (\$m, \$n) = @_;
> if (\$n == 1) {
> return \$m;
> }
> return \$m + multiply_em(\$m, \$n - 1);
>}

yes, this is pretty much the same as:

for \$x = 1; \$x < \$n; \$x++ {
count += \$m
}

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post vamsi C Programming 21 03-09-2009 10:53 PM n00m C++ 12 03-13-2008 03:18 PM gpi5 VHDL 1 11-09-2004 02:44 PM Xiangliang Meng C++ 1 06-21-2004 03:11 AM dmattis C Programming 64 11-02-2003 01:39 PM

Advertisments