Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

Re: problem prototyping a self-recursing function

by frankus (Priest)
on Dec 07, 2001 at 16:26 UTC ( #130179=note: print w/replies, xml ) Need Help??

in reply to problem prototyping a self-recursing function

You probably already know this, or perhaps don't need to hear it.
Recursion makes for biig overheads, and without exception anything using recursion can be done with loops.

Part of the reason that people use recursion is to map the solution precisely to the problem set,
this is often due to not understanding the problem, although I'm not implying this is the case here.
i.e Using your simple example.

#!/usr/local/bin/perl -w use strict; sub main() { doSomething(1,2,0); print "Done\n"; } sub doSomething{ my ($data1, $data2, $count)=@_; for($count..3){ $data1++,$data2++,$count++; print "\$data1: $data1, \$data2: $data2, \$count: $cou +nt\n"; } } main()

Now this is probably redundant information, or at worst seems like bigotry, but
believe me, I've used recursion in LISP for years, but whilst I enjoyed it, it's not effecient.

If you're just doing this as an exercise in recursion, that's fine, otherwise I'd advocate developing
a loop alternative and benchmarking the two, the dividends should speak for themselves.


Brother Frankus.


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

    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

      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://130179]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (3)
As of 2018-06-24 11:56 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (126 votes). Check out past polls.