(jeffa) Re: Recursion
by jeffa (Bishop) on Nov 15, 2000 at 00:30 UTC
|
Depends. Each recursive call to function places another entry
on the system stack. So it's possible to 'crash the stack' if
you get stuck in a loop.
Some problems are best suited for recursion - like traversing
a file system. You don't know how many levels you will descend,
so leave that up to recursion.
The same problem can be solved with a while loop, but only
if you implement your own stack.
Keep in mind that the faster solution (in general - always exceptions) will be a loop, and
for that matter, if you can find a formula to replace the loop,
then you will really increase the speed.
Example, summing a list of consecutive numbers, starting with 1:
my @numbs = qw(1 2 3 4 5 6 7 8 9 10);
# loop style
sub loop {
my $numbs = shift;
my $sum;
map { $sum += $_; } @{$numbs};
return $sum;
}
# recursive style - warning: destroys array
sub recurse {
my ($numbs, $sum) = @_;
if (scalar @{$numbs}) {
$sum += pop @{$numbs};
&recurse($numbs, $sum);
}
else {
return $sum;
}
}
Both are trivial for this example - and execute in about
the same time:
Benchmark: timing 100000 iterations of Loop, Recursive...
Loop: 1 wallclock secs ( 0.70 usr + 0.00 sys = 0.70 CPU)
Recursive: 1 wallclock secs ( 0.68 usr + 0.00 sys = 0.68 CPU)
But, a relatively famous person by the name of Gauss will
tell you that this problem can be solved in one fell swoop
with:
Benchmark: timing 100000 iterations of Guass...
Guass: 1 wallclock secs ( 0.49 usr + 0.00 sys = 0.49 CPU)
Thanks to myocom and FouRPlaY for help on the Gauss formula. | [reply] [d/l] [select] |
|
"Implementing your own stack" is trivial in Perl. I think
this argument applies more to C where you don't already
have efficient, self-growing lists handy.
If you may need to recurse very deeply, then you may be
better off implementing your own stack since it will likely
be more compact.
As for the original question of which works better in
Perl... I think Perl supports both quite well, better than
many languages (like making it trivial to implement your
own stack).
Here are what I see as the main trade-offs. Recursion is
usually easier to write correctly the first time. Looping
is usually more efficient in space and time (ie. faster and
uses less memory). Recursion makes it hard to be flexible
in the interface you provide -- you either return a big
list or make the user provide call-backs. Looping lets you
provide iterators.
So it is often best to start with a recursive method.
Later, if you need more speed or less memory consumption,
then you can do the extra work to switch to looping. Also,
if you provide your code for others to use (for example,
by creating a module), then you might want to do the
extra work to switch to looping and provide a more flexible
interface (and more efficiency).
But if you know you plan to make this available to others
or suspect that efficiency will be unusually important here,
then you may want to analyze how you'd solve the problem
without recursion to see if you want to start off that way
and avoid having to convert later.
Also, by allowing an "iterator" interface, "looping" may
allow you to deal with problems that are too big to deal
with (naively) recursively. For example, finding all
permutations is very quick to code recusively. But most
such will just return a list of all permutations. It is
trivial to feed a rather small list to these routines and
exhaust memory. A non-recursive routine would likely
allow you to repeatedly request the "next permutation"
so you could eventually "deal with" them all without having
to try to store them all.
You could "fix" such a recursive routine by teaching it to
call a user call-back function for each permutation found.
But this just forces users of your code into an
often-inconvenient method of coding. Better to spend
that effort making your code non-recursive with an
interator interface.
-
tye
(but my friends call me "Tye")
| [reply] |
|
Are you thinking of the sum of the first N natural numbers?
I've heard the legend/story that he (Guass) came up with this when he was somewhere between 10 and 15 years old (for the record, I might have come up with this when I was 10, but cartoons were more interesting than math then).
Anyway, it's S=N*(N+1)/2
FouRPlaY
Learning Perl or Going To Die Trying
| [reply] |
|
It's quite possible that Gauss figured that out when he was
young. I actually figured it out when I was 8. Being a
young, anti-social kid, I tried adding numbers between 1
and as high as I could go, trying to find a pattern. The
funny part was that I didn't know what variables were,
although I did know fractions. My formula was something
like, "Take a number, add one, divide by two, and then
multiply it by half of the original number." It seemed
very strange to me that that formula seemed to hold for
any number I gave it. One day I even added all the numbers
up to 20 in my hand to see if I got 210.
Anyway, one day I told my math teacher that I figured out
this neat formula and then she introduced me to concepts
like "variables" and "functions". :)
-Ted
| [reply] |
|
RE: Recursion
by clemburg (Curate) on Nov 15, 2000 at 15:23 UTC
|
First, I agree with what has been said by merlyn and the majority of the other posters: in general, your question can't be answered, since it is meaningless without mentioning a concrete problem.
This said, one could argue that Perl is not as well suited to recursive solutions as some other languages are, since it's function call implementation places a comparatively large load on the system in terms of memory and execution speed. Perl is simply not optimized for recursion, but for other operations (e.g., text manipulation and file IO).
For some more exact data on this, have a look at Timing Trials, or, the Trials of Timing: Experiments with Scripting and User-Interface Languages, a research paper that compares the performance of C, Awk, Perl, Tcl, Java, Visual Basic, Limbo and Scheme on different platforms for loops and arithmetic, function calls (using the heavily recursive Ackermann function), arrays and strings, associative data structures, input/output, graphical user interfaces, and compilation vs. interpretation.
Christian Lemburg
Brainbench MVP for Perl
http://www.brainbench.com
| [reply] |
Re: Recursion
by fundflow (Chaplain) on Nov 15, 2000 at 01:13 UTC
|
It seems like the post asks about the following:
Some languages were designed (in the 70s) with recursion
methodology in mind. Like Lisp. These had special constructs to
convert the recursion into highly optimized OPs. Some special
hardware was built for this as well. (remember 'tail recursion'?)
With this respect, and to my best knowledge, Perl does not
supply any of these special constructs/optimizations. So just
do whatever works for you, or whatever is more natural for the
problem.
| [reply] |
|
Actually Lisp was invented in the 50's.
In fact Lisp was the first interpreted language built.
Literally they were developing it, and had a manual process
for turning Lisp into assembly. Someone wrote 'eval' in
Lisp. Someone else noticed that it would be really neat if
you translated that into assembly, and away it went!
Programmers associate this stuff with the 70's because that
was when the first mainstream programming langauges that
supported recursion (like C) became popular.
| [reply] |
|
I would not call it 'recursion methodology.' LISP is usually referred to as functional language, hence the ease with which recursion is implemented. In LISP, recursion is intuitive and more often than not the right solution.
LISP is fun. :)
| [reply] |
Re: Recursion
by merlyn (Sage) on Nov 15, 2000 at 00:27 UTC
|
| [reply] |
|
I disagree, most looping problems can be made into a recursive function and vise versa.
--=Lolindrath=--
| [reply] |
|
Don't think of it in terms of the suitability for the language. Perl can do either just as well as any other language. Think of it in terms of the problem you're trying to solve. Does it make more sense to use a recursive algorithm or an iterative one? Perl is fine either way, like most languages.
| [reply] |
|
| [reply] |
RE: Recursion
by PsychoSpunk (Hermit) on Nov 15, 2000 at 03:45 UTC
|
The trusted rule of thumb that I use:
Use recursion if you have a large chunk of something that
you're going to do something to repeatedly while using smaller
chunks of that large chunk. In other words, recursion's best
used when you have a large unmanagable chunk that has enough
regularity to be managable in smaller chunks.
For all other cases of repitition, use loops.
ALL HAIL BRAK!!! | [reply] |
RE: Recursion
by lhoward (Vicar) on Nov 15, 2000 at 17:22 UTC
|
Here's my take on it:
There are some problems that are better suited to recursion
and some that are better suited to looping. Some languages
don't give you a choice (for example COBOL has no recursion, ML has
no looping). Perl lets you choose. However, it should be
noted that a non-recursive solution to a problem is usually
at least marginally faster than a recursive solution.
But when you convert a recursive algorithm to a non-recursive
equivalent you normally end up writing a lot more code and
making your program harder to read and support (i've seen
20 lines of recursive code become 200+ lines of non-recursive code). So unless
you have a good reason to optimize out the recursion
leave it in. | [reply] |
|
> ML has no looping
That is not at all true. ML has a while
construction similar to those in
C and Perl. Also, the map looping operator
is implemented internally with a loop, and any tail-recursive functions that
the programmer defines are optimized internally to loops.
| [reply] |
Re: Recursion: An example of Looping and Recursion
by lolindrath (Scribe) on Nov 16, 2000 at 07:15 UTC
|
This is the Euclidean algorithm for finding the Greatest common divisor between two numbers. I thought I'd throw a bit of my own code into the fray. The first one uses a loop, the second uses recursion. Could someone benchmark this for me?
#!/usr/bin/perl -w
print "GCD: " . GCD( 45, 5 ) . " RecGCD: " . RecGCD( 45, 5 ) . "\n";
#Assumes $A is the largest number
sub GCD
{
$A = shift;
$B = shift;
$R = 1;
while ( $R != 0 )
{
$R = $A % $B;
if ( $R == 0 )
{
return $B;
}
$A = $B;
$B = $R;
}
}
#Assumes $A is the largest number
sub RecGCD
{
$A = shift;
$B = shift;
$R = 0;
$R = $A % $B;
if ( $R == 0 )
{
return $B;
}
RecGCD( $B, $R );
}
--=Lolindrath=-- | [reply] [d/l] |
|
Whoop! a benchmark question! Ahhh...
# for 45, 5
Rate loop recur
loop 30118/s -- -37%
recur 47528/s 58% --
# for 296, 111
Rate recur loop
recur 9303/s -- -36%
loop 14426/s 55% --
# for 298, 111
Rate recur loop
recur 4672/s -- -45%
loop 8445/s 81% --
Interesting what a win the loop version is on that
last one...
--
$you = new YOU;
honk() if $you->love(perl) | [reply] |