Re: Misunderstanding Recursion

it should run a lot faster/be more efficient than the latter

While recursion may make for much simpler code, it will not necessarily make for faster/more efficient code tail recursion is better in this regard. A classic example is calculation of factorials. In my, doubtless horrid, example:

#!perl

use strict;
use warnings;
use diagnostics;

use Benchmark qw(:all);

#print 'looping: ' . looping(10) . "\n";
#print 'recursive: ' . recursive(10) . "\n";

my $count = -5;

cmpthese($count,{
    recursive => sub{&recursive(50)},
    looping => sub{&looping(50)}});

sub recursive
    {

    my $x = shift;

    if($x <= 1) {
        return 1;
    }
    else{
        return $x * recursive($x - 1);
    }
    }

sub looping
    {
    my $x = shift;

    my $y = 1;

    foreach my $z (1 .. $x) {
        $y*=$z;
    }

    return $y;
}
[download]

I got these results:

             Rate recursive   looping
recursive  9228/s        --      -77%
looping   39979/s      333%        --
[download]

Which, if I interpret it correctly, shows the looping sub is quite a bit faster.

Of course, this does not mean that all recursive routines that can be replaced by iterative routines should be; this is likely to be misplaced optimization. There are a great number of cases where the code written with recursion is going to be much simpler, which means that it will globally be better: more reliable, easier to test, easier to understand, quicker to get right.

emc

At that time [1909] the chief engineer was almost always the chief test pilot as well. That had the fortunate result of eliminating poor engineering early in aviation.

—Igor Sikorsky, reported in AOPA Pilot magazine February 2003.

Comment on Re: Misunderstanding Recursion Select or Download Code

Replies are listed 'Best First'.
Re^2: Misunderstanding Recursion by ikegami (Patriarch) on Dec 16, 2006 at 00:29 UTC
The multiplication happens after the recursive call in your snippet, so your snippet isn't tail recursive. The following is a tail recursive version of your snippet: `sub _tail_recur { my ($x, $y) = @_; if ($x <= 1) { return $y; } else { return _tail_recur($x - 1, $x * $y); } } sub tail_recur { my ($x) = @_; return _tail_recur($x, 1); }` [download] Tail recursion allows for the compiler to automatically flatten recursion (slow, and memory usage is proportional to the recursion depth) into a loop (fast, and memory usage is constant). Unfortunately, Perl5 does not do tail-recursion optimization.	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: Misunderstanding Recursion
by ikegami (Patriarch) on Dec 16, 2006 at 00:29 UTC

The multiplication happens after the recursive call in your snippet, so your snippet isn't tail recursive. The following is a tail recursive version of your snippet:

sub _tail_recur {
   my ($x, $y) = @_;

   if ($x <= 1) {
      return $y;
   } else {
      return _tail_recur($x - 1, $x * $y);
   }
}

sub tail_recur {
   my ($x) = @_;
   return _tail_recur($x, 1);
}
[download]

Tail recursion allows for the compiler to automatically flatten recursion (slow, and memory usage is proportional to the recursion depth) into a loop (fast, and memory usage is constant). Unfortunately, Perl5 does not do tail-recursion optimization.

[reply]
[d/l]