recursive functions

S

steve_f

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

Sam Holden

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

steve_f

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

Richard Gration

"steve_f" said:
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
 
A

Abhinav

steve_f said:
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
 
A

Anno Siegel

steve_f said:
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
 
A

Anno Siegel

[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
 
A

Anno Siegel

Richard Gration said:
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
 
S

steve_f

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!
 
S

steve_f

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

Richard Gration

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
 
S

Sherm Pendley

steve_f said:
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--
 
A

Anno Siegel

Richard Gration said:
[...]

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
 
T

thundergnat

Abhinav said:
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 '..';
}
 
B

Bill Smith

Anno Siegel said:
[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
 
A

Anno Siegel

Bill Smith said:
Anno Siegel said:
[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
 
T

Tom Regner

steve_f said:
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
;)
 
R

Richard Gration

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
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!
You weren't taught to do that recursively, I suppose :)

The mind boggles ... ;-)

Rich
 
S

steve_f

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 ;-)
 
D

David Combs

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,
and read the reader-reviews.

David
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,898
Latest member
BlairH7607

Latest Threads

Top