(jeffa) Re: Recursion

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

}
[download]

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)
[download]

But, a relatively famous person by the name of Gauss will tell you that this problem can be solved in one fell swoop with:

n(n+1) / 2

Benchmark: timing 100000 iterations of Guass...
    Guass:  1 wallclock secs ( 0.49 usr +  0.00 sys =  0.49 CPU)
[download]

Thanks to myocom and FouRPlaY for help on the Gauss formula.

Comment on (jeffa) Re: Recursion Select or Download Code

Replies are listed 'Best First'.
(tye)Re: Recursion by tye (Sage) on Nov 15, 2000 at 00:57 UTC
"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]
RE: Re: Recursion by FouRPlaY (Monk) on Nov 15, 2000 at 01:11 UTC
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]
Sum of numbers between 1 and N by tedv (Pilgrim) on Nov 15, 2000 at 21:42 UTC
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: Sum of numbers between 1 and N by husker (Chaplain) on Nov 15, 2000 at 22:20 UTC
Gauss did indeed figure this out at the age of 8 .. a teacher had given her unruly class the "busywork" problem of summing the first 100 integers. Gauss is also notorious for catching errors in his father's bookkeeping at an even earlier age. This from A Biography of Gauss	[reply]


Perl: the Markov chain saw
	PerlMonks