Recursion

[lolindrath]

In my Fundementals of Computer Science class we've studied recursive programming techniques. Since then I've been seeing recursive solutions to many of my programming problems.
My question is, which is better, looping or recursing? Which is more suited for Perl?
Thanks

--=Lolindrath=--

[jeffa]

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

}

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)

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)

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

[tye]

"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")

[FouRPlaY]

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

[tedv]

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

[clemburg]

First, I agree with what has been said by merlyn and the majority of the other posters: in general, your question can't be answered, since it is meaningless without mentioning a concrete problem.

This said, one could argue that Perl is not as well suited to recursive solutions as some other languages are, since it's function call implementation places a comparatively large load on the system in terms of memory and execution speed. Perl is simply not optimized for recursion, but for other operations (e.g., text manipulation and file IO).

For some more exact data on this, have a look at Timing Trials, or, the Trials of Timing: Experiments with Scripting and User-Interface Languages, a research paper that compares the performance of C, Awk, Perl, Tcl, Java, Visual Basic, Limbo and Scheme on different platforms for loops and arithmetic, function calls (using the heavily recursive Ackermann function), arrays and strings, associative data structures, input/output, graphical user interfaces, and compilation vs. interpretation.

Christian Lemburg
Brainbench MVP for Perl
http://www.brainbench.com

[fundflow]

It seems like the post asks about the following:

Some languages were designed (in the 70s) with recursion methodology in mind. Like Lisp. These had special constructs to convert the recursion into highly optimized OPs. Some special hardware was built for this as well. (remember 'tail recursion'?)

With this respect, and to my best knowledge, Perl does not supply any of these special constructs/optimizations. So just do whatever works for you, or whatever is more natural for the problem.

[tilly]

Actually Lisp was invented in the 50's.

In fact Lisp was the first interpreted language built. Literally they were developing it, and had a manual process for turning Lisp into assembly. Someone wrote 'eval' in Lisp. Someone else noticed that it would be really neat if you translated that into assembly, and away it went!

Programmers associate this stuff with the 70's because that was when the first mainstream programming langauges that supported recursion (like C) became popular.

[dmitri]

I would not call it 'recursion methodology.' LISP is usually referred to as functional language, hence the ease with which recursion is implemented. In LISP, recursion is intuitive and more often than not the right solution.

LISP is fun. :)

[merlyn]

Which is better, a car or a truck? You're comparing apples and, uh, IBMs here.

-- Randal L. Schwartz, Perl hacker

[lolindrath]

I disagree, most looping problems can be made into a recursive function and vise versa.

--=Lolindrath=--

[Fastolfe]

Don't think of it in terms of the suitability for the language. Perl can do either just as well as any other language. Think of it in terms of the problem you're trying to solve. Does it make more sense to use a recursive algorithm or an iterative one? Perl is fine either way, like most languages.

[merlyn]

Yes, and most cars can be used as trucks, and most trucks can be used as cars. Questions with "better" are rarely answerable until we understand what the context is, and what you're optimizing for.

-- Randal L. Schwartz, Perl hacker

[PsychoSpunk]

The trusted rule of thumb that I use:

Use recursion if you have a large chunk of something that you're going to do something to repeatedly while using smaller chunks of that large chunk. In other words, recursion's best used when you have a large unmanagable chunk that has enough regularity to be managable in smaller chunks.

For all other cases of repitition, use loops.

ALL HAIL BRAK!!!

[lhoward]

Here's my take on it:

There are some problems that are better suited to recursion and some that are better suited to looping. Some languages don't give you a choice (for example COBOL has no recursion, ML has no looping). Perl lets you choose. However, it should be noted that a non-recursive solution to a problem is usually at least marginally faster than a recursive solution. But when you convert a recursive algorithm to a non-recursive equivalent you normally end up writing a lot more code and making your program harder to read and support (i've seen 20 lines of recursive code become 200+ lines of non-recursive code). So unless you have a good reason to optimize out the recursion leave it in.

[Dominus]

> ML has no looping

That is not at all true. ML has a while construction similar to those in C and Perl. Also, the map looping operator is implemented internally with a loop, and any tail-recursive functions that the programmer defines are optimized internally to loops.

[lolindrath]

This is the Euclidean algorithm for finding the Greatest common divisor between two numbers. I thought I'd throw a bit of my own code into the fray. The first one uses a loop, the second uses recursion. Could someone benchmark this for me?


#!/usr/bin/perl -w


print "GCD: " . GCD( 45, 5 ) . " RecGCD: " . RecGCD( 45, 5 ) . "\n";

#Assumes $A is the largest number
sub GCD 
{
    $A = shift;
    $B = shift;
    $R = 1;
    
    while ( $R != 0 )
    {
        $R = $A % $B;
        
        if ( $R == 0 )
        {
            return $B;
        }
        
        $A = $B;
        $B = $R;
    }
}


#Assumes $A is the largest number
sub RecGCD
{
    $A = shift;
    $B = shift;
    $R = 0;
    
    $R = $A % $B;
    
    if ( $R == 0 )
    {
        return $B;
    }
    
    RecGCD( $B, $R );    
}



--=Lolindrath=--

[extremely]

Whoop! a benchmark question! Ahhh...

# for 45, 5
         Rate  loop recur
loop  30118/s    --  -37%
recur 47528/s   58%    --

# for 296, 111
         Rate recur  loop
recur  9303/s    --  -36%
loop  14426/s   55%    --

# for 298, 111
        Rate recur  loop
recur 4672/s    --  -45%
loop  8445/s   81%    --

Interesting what a win the loop version is on that last one...

--
$you = new YOU;
honk() if $you->love(perl)