# recursive functions

Discussion in 'Perl Misc' started by steve_f, Aug 4, 2004.

1. ### steve_fGuest

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.

steve_f, Aug 4, 2004

2. ### Sam HoldenGuest

On Wed, 04 Aug 2004 08:59:12 -0400, steve_f <> 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

Sam Holden, Aug 4, 2004

3. ### steve_fGuest

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;
}

steve_f, Aug 4, 2004
4. ### Richard GrationGuest

In article <>, "steve_f"
<> 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

Richard Gration, Aug 4, 2004
5. ### AbhinavGuest

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

Abhinav, Aug 4, 2004
6. ### Anno SiegelGuest

steve_f <> 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, Aug 4, 2004
7. ### Anno SiegelGuest

Abhinav <> 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, Aug 4, 2004
8. ### Anno SiegelGuest

Richard Gration <> wrote in comp.lang.perl.misc:
> In article <>, "steve_f"
> <> 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

Anno Siegel, Aug 4, 2004
9. ### steve_fGuest

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, Aug 4, 2004
10. ### steve_fGuest

On Wed, 04 Aug 2004 12:09:50 -0400, steve_f <> 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
}

steve_f, Aug 4, 2004
11. ### Richard GrationGuest

In article <cer0qa\$4um\$-Berlin.DE>, "Anno Siegel"
<-berlin.de> wrote:

> Richard Gration <> wrote in comp.lang.perl.misc:
>> 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

But you have to agree it illustrates the concept of recursion well. A
computer is not the ideal tool to convert celsius to fahrenheit either,
yet I have written a few programs to do just that when learning a
language.

Rich

Richard Gration, Aug 4, 2004
12. ### Sherm PendleyGuest

steve_f wrote:

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

To bring it back on-topic, then, you might want to have a look at
O'Reilly's "Mastering Algorithms with Perl". A number of recursive
algorithms are discussed in it.

sherm--

--
Cocoa programming in Perl: http://camelbones.sourceforge.net
Hire me! My resume: http://www.dot-app.org

Sherm Pendley, Aug 4, 2004
13. ### Anno SiegelGuest

Richard Gration <> wrote in comp.lang.perl.misc:
> In article <cer0qa\$4um\$-Berlin.DE>, "Anno Siegel"
> <-berlin.de> wrote:

> > Richard Gration <> wrote in comp.lang.perl.misc:
> >> The absolute classic example of a recursive algorithm is the factorial
> >> function. ...

[...]

> But you have to agree it illustrates the concept of recursion well. A

The factorial example illustrates the *mechanics* of recursion. But so
do summing up (instead of multiplying) the first integers, or counting
the elements in a list, or a dozen tasks that can be done recursively,
but are best done iteratively, in Perl and most other languages.

It does nothing to help develop judgment of when recursion is an
appropriate solution, and where it's only (possibly expensive)
claptrap. In everyday programming, the most frequent question
about recursion is whether to use it at all. The factorial
example teaches the wrong decision.

If you want a simple arithmetic example for a naturally recursive
problem, use Euclid's algorithm.

sub euclid {
my ( \$a, \$b) = @_;
\$b ? euclid( \$b, \$a % \$b) : \$a;
}

> computer is not the ideal tool to convert celsius to fahrenheit either,

Why on earth not? Would you prefer a slide-rule? It isn't used to
its full capacity, for sure, but that's something else.

> yet I have written a few programs to do just that when learning a
> language.

You weren't taught to do that recursively, I suppose

Anno

Anno Siegel, Aug 4, 2004
14. ### thundergnatGuest

Abhinav wrote:

> 4. Directory search of a file system

Heres something I had done at one point.
This could be MUCH more efficiently done with File::Find
but I wrote this to noodle around with recursion.

Print a manifest of a directory tree with file sizes to a file
\$dir.mft.

#!/usr/bin/perl
use strict;
use warnings;
use Cwd;

my \$dir = \$ARGV[0];
die "You must specify a starting directory" unless \$dir;
\$dir =~ m/[\\\/](\w+)[\\\/]?\$/;
die "Bad directory name: \$dir" unless \$1;
my \$name = \$1.".mft";
my \$cwd = getcwd;
my (\$indent,\$index,@mfst);
my \$space = '';

mft(\$dir);

chdir \$cwd;
open my \$MFST, ">\$name" or die "Could not open file \$!";
print \$MFST "Manifest for \$dir.\n\n";
print \$MFST @mfst;

sub mft{
my \$dir = shift;
\$indent += 2;
chdir \$dir;
my @list = glob("*");
foreach my \$file(@list) {
if (-d \$file){
push @mfst, (' ' x \$indent).\$file."\n";
mft(\$file);
}else{
push @mfst, (' ' x \$indent).\$space.\$file.' '.
(((-s \$file)>1024) ?
(sprintf "%.1f", (-s \$file)/1024)."K\n" :
(sprintf "%d", (-s \$file))."B\n");
}
}
\$indent -= 2;
chdir '..';
}

thundergnat, Aug 4, 2004
15. ### Bill SmithGuest

"Anno Siegel" <-berlin.de> wrote in message
news:ceqvfh\$3ot\$-Berlin.DE...
> Abhinav <> 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.
>

Recursion provides a way to SPECIFY many functions (including all of
these examples) briefly, yet completely. Computer languages, which
support recursion, allow us to implement these directly without the
effort to find and validate a non-recursive solution. We usually pay a
heavy price in both speed and memory for this convenience.

The factorial function belongs on this list because the beginner can
evaluate the pros and cons of both methods.

Bill

Bill Smith, Aug 5, 2004
16. ### Anno SiegelGuest

Bill Smith <> wrote in comp.lang.perl.misc:
>
> "Anno Siegel" <-berlin.de> wrote in message
> news:ceqvfh\$3ot\$-Berlin.DE...
> > Abhinav <> 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.
> >

>
>
>
> Recursion provides a way to SPECIFY many functions (including all of
> these examples) briefly, yet completely.

Why would anyone want to specify the factorial recursively? It's the
product of the first n natural numbers.

> Computer languages, which
> support recursion, allow us to implement these directly without the
> effort to find and validate a non-recursive solution. We usually pay a
> heavy price in both speed and memory for this convenience.

If the specification isn't recursive, there's no need to find a
non-recursive solution.

> The factorial function belongs on this list because the beginner can
> evaluate the pros and cons of both methods.

It belongs on a second list that demonstrates problems that *can* be
solved recursively, but are better treated otherwise.

Anno

Anno Siegel, Aug 5, 2004
17. ### Tom RegnerGuest

Re: recursive functions [Silly Joke]

steve_f wrote:
> I could never really wrap my mind around the concept
> of recursive functions.

That's because:
To Know Recursion, You Must First Know Recursion...

sorry, couldn't resist

--
Dievision GmbH | Kriegerstrasse 44 | 30161 Hannover
Telefon: (0511) 288791-0 | Telefax: (0511) 288791-99
http://www.dievision.de

Tom Regner, Aug 5, 2004
18. ### Richard GrationGuest

In article <cercpd\$bn1\$-Berlin.DE>, "Anno Siegel"
<-berlin.de> wrote:
<SNIP>
> In everyday programming, the most frequent question about recursion is
> whether to use it at all. The factorial example teaches the wrong
> decision.

Fair point. Agreed.

> If you want a simple arithmetic example for a naturally recursive
> problem, use Euclid's algorithm.
>
> sub euclid {
> my ( \$a, \$b) = @_;
> \$b ? euclid( \$b, \$a % \$b) : \$a;
> }
>

That's beautiful ... noted for future reference

>> computer is not the ideal tool to convert celsius to fahrenheit

either,
>
> Why on earth not?

the overkill factor ... put another way ... (possibly expensive) claptrap ? ;-)

> Would you prefer a slide-rule? It isn't used to its

well, when I wrote the above comment, a long strip of paper with 2
columns of marks with numbers next to them was one tool which came to
mind!

>> yet I have written a few programs to do just that when learning a
>> language.

> You weren't taught to do that recursively, I suppose

The mind boggles ... ;-)

Rich

Richard Gration, Aug 5, 2004
19. ### steve_fGuest

I just want to thank everyone one more time...very interesting
discussion...now I have to examine my programming and
see if any problems require a recursive solution ;-)

steve_f, Aug 9, 2004
20. ### David CombsGuest

In article <>,
Sherm Pendley <> wrote:
>steve_f wrote:
>
>> hmmmm....!! ok, yes this post was off topic, I really should of found a
>> programming group!

>
>To bring it back on-topic, then, you might want to have a look at
>O'Reilly's "Mastering Algorithms with Perl". A number of recursive
>algorithms are discussed in it.

I think he'd be a lot better off getting one or several
standard algorithms texts --- over the last 20 or so years there's
been so very many good ones!

Go to amazon and search, I guess, for "algorithms" or the like,