if I write a recursive procedure like factorial_iterative ... does it's memory usage grow linearly the way factorial_recursive looks like it should.
Yep, since it's just a wrapper around a recursive sub, fi_helper. Recursion isn't terribly efficient in perl since function calls aren't too swift and take up a fair bit of memory (hence the recusion warning (see. perldiag)). An iterative approach however will be a bit quicker e.g
use strict;
use Benchmark 'cmpthese';
my $limit = @ARGV ? shift : 100;
cmpthese(-10, {
recurse => sub { rec($limit) },
iterate => sub { itr($limit) },
});
sub rec {
my $n = shift;
return $n == 1 ? return 1 : $n * rec($n - 1);
}
sub itr {
my($n, $r) = (shift, 1);
$r *= $n-- while $n > 1;
return $r;
}
__output__
Benchmark: running iterate, recurse for at least 10 CPU seconds...
iterate: 11 wallclock secs (10.58 usr + 0.00 sys = 10.58 CPU) @ 58
+14.45/s (n=61546)
recurse: 11 wallclock secs (10.23 usr + 0.00 sys = 10.23 CPU) @ 16
+77.45/s (n=17162)
Rate recurse iterate
recurse 1677/s -- -71%
iterate 5814/s 247% --
Of course all benchmarks are to be taken with a grain of salt, but I think this gives a pretty clear illustration of the hit recursion incurs.
HTH
_________
broquaint | 