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

[download]

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

In reply to Re: Re: problem prototyping a self-recursing function by thraxil
in thread problem prototyping a self-recursing function by apprentice

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.