Re: Re: Iterative vs Recursive Processes

Thanks! I should have mentioned that I had read that post and the very interesting Pure Perl tail call optimization in my RTFM search prior to my post. I wasn't able to find an answer to my question, which is simply whether if I write a recursive procedure like factorial_iterative, which looks like it ought to generate an iterative process, does it in fact execute in a constant memory space like it looks like it should, or does it's memory usage grow linearly the way factorial_recursive looks like it should.

Perhaps my question is foolish and someone wiser than I could show me the error of my ways.

Comment on Re: Re: Iterative vs Recursive Processes

Replies are listed 'Best First'.
Re: Re: Re: Iterative vs Recursive Processes by broquaint (Abbot) on May 12, 2003 at 18:06 UTC
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% -- [download] 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`	[reply] [d/l]
Re: Re: Re: Iterative vs Recursive Processes by suaveant (Parson) on May 12, 2003 at 16:41 UTC
I couldn't say... but the way I would test would be to give each one a very large number and watch the process with 'top' to follow its memory usage. Should give you a good idea. - Ant - Some of my best work - (1 2 3)	[reply]