http://www.perlmonks.org?node_id=130296


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.

    ¤