Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling

Re: Re: problem prototyping a self-recursing function

by thraxil (Prior)
on Dec 08, 2001 at 00:15 UTC ( #130296=note: print w/replies, xml ) Need Help??

in reply to Re: problem prototyping a self-recursing function
in thread problem prototyping a self-recursing function

here's a benchmark of the two:

#!/usr/bin/perl -w use strict; use Benchmark; my $trials = 50000; timethese($trials, { 'recursive' => sub {doSomethingRec(2,2,0);}, 'loop' => sub {doSomethingLoop(2,2,0);} }); sub doSomethingRec { my ($data1, $data2, $count) = @_; print "\$data1: $data1, \$data2: $data2, \$count: $count\n"; $data1++, $data2++, $count++; if ($count < 4) { doSomethingRec($data1, $data2, $count); } } sub doSomethingLoop { my ($data1, $data2, $count)=@_; for($count..3){ $data1++,$data2++,$count++; print "\$data1: $data1, \$data2: $data2, \$count: $cou +nt\n"; } }

the results on my system (1GHz P4 w/ 512MB) for $trials = 50000:

      loop:  3 wallclock secs ( 2.09 usr +  0.01 sys =  2.10 CPU) @ 23809.52/s (n=50000)
 recursive:  2 wallclock secs ( 2.19 usr +  0.01 sys =  2.20 CPU) @ 22727.27/s (n=50000)

for $trials = 500000:

      loop: 21 wallclock secs (20.91 usr +  0.06 sys = 20.97 CPU) @ 23843.59/s (n=500000)
 recursive: 23 wallclock secs (21.89 usr +  0.09 sys = 21.98 CPU) @ 22747.95/s (n=500000)

so i'd be inclined to say that there isn't really a very significant difference between the looped and recursive versions in this case (not surprising since the subroutine doesn't return anything and thus the perl interpreter ought to be able to optimize things fairly well).

of course, things change a little if you increase the level of recursion. eg, changing it to $count < 40 in the recursive one and to $count..39 in the loop version (and $trials = 50000):

      loop: 17 wallclock secs (16.46 usr +  0.09 sys = 16.55 CPU) @ 3021.15/s (n=50000)
 recursive: 24 wallclock secs (23.48 usr +  0.12 sys = 23.60 CPU) @ 2118.64/s (n=50000)

increase the level of recursion much more and you run into the real problem of doing recursion in perl. it limits the level of recursion so you start getting runtime errors if you go over something like 50 deep (i'm not sure exactly what the level is). IMO, this, not the efficiency reason, is why you may want to avoid heavy use of recursion in perl.

the issue of loop vs recursion efficiency is highly dependent on the language used. it's been my experience with functional languages like ML that recursion is significantly more efficient than looping because the language is designed for it and the compiler/interpreter is optimized for recursion. i haven't done much LISP programming but i'm surprised that you had efficiency problems with recursion; i thought it was one of those recursion optimized languages.

anders pearson

Replies are listed 'Best First'.
Re: Re: Re: problem prototyping a self-recursing function
by frankus (Priest) on Dec 08, 2001 at 00:51 UTC

    I might have appeared zealous but I was not decrying recursion as being all bad; just advocating discretion in it's use.

    We had a LISP lecturer who made grown men blubber if their reursive functions were over 3 lines<br and used sarcasm if iterative solutions were suggested....
    /me shudders at the memory of his sarcasm


    Brother Frankus.


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://130296]
[Lady_Aleena]: File::Find doesn't have a simple sub wanted example, like get the name of the file.
[Discipulus]: there is also find2perl with your perl installation
[Discipulus]: and in the wanted sub you just calculate the duretion and add it the total, stop
[shmem]: sub wanted { push @files, $File::Find::name if $File::Find::name =~/\.mp3$/ }
[Lady_Aleena]: shmem, that is understandable! The two examples in File::Find don't make sense to me on a quick glance.

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (12)
As of 2017-04-23 20:52 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (432 votes). Check out past polls.