Re: Misunderstanding Recursion

Just to add to the general discussion, you can sometimes simulate tail recursion optimization by setting the argument list and using goto function:

sub some_function {
  ...
  @_ = @new_list_of arguments
  goto &some_function
  ...
}
[download]

But even this is not very efficient in Perl compared to iteration and normal recursion (though if the recursion is deep, this is an option...though iteration is most likely a better option). (Update: so it could be considered a memory optimization over normal recursion, but definitely not a speed optimization).

Comment on Re: Misunderstanding Recursion Download Code

Replies are listed 'Best First'.
Re^2: Misunderstanding Recursion by pKai (Priest) on Dec 16, 2006 at 21:49 UTC
…this is not very efficient in Perl… You may refer to some disappointing benchmark as this: `Rate goto_recur recursive tail_recur looping goto_recur 3437/s -- -59% -60% -90% recursive 8472/s 147% -- -1% -76% tail_recur 8569/s 149% 1% -- -76% looping 35417/s 931% 318% 313% --` [download] where the benchmark is that of swampyankee above, adding ikegami's `tail_recur` and a derived version of that using your goto recipe: `sub _goto_recur { my ($x, $y) = @_; if ($x <= 1) { return $y; } else { @_ = ($x - 1, $x * $y); goto &_goto_recur; } } sub goto_recur { my ($x) = @_; return _goto_recur($x, 1); }` [download] Then I was surprised that throwing out all lexicals and directly messing with `@_` yields more pleasing results: `sub _goto_recur { if ($_[0] <= 1) { return $_[1]; } else { $_[1] *= $_[0]; --$_[0]; goto &_goto_recur; } } sub goto_recur { my ($x, $y) = (shift, 1); # We can't plug the constant 1 directly into $_[1] # since we want to change that (alias!) return _goto_recur($x, $y); }` [download] Gives on my machine: `Rate recursive tail_recur goto_recur looping recursive 8456/s -- -1% -9% -77% tail_recur 8519/s 1% -- -8% -76% goto_recur 9278/s 10% 9% -- -74% looping 36011/s 326% 323% 288% --` [download] Of course that code does not look very desirable from a maintainers point of view.	[reply] [d/l] [select]
Re^3: Misunderstanding Recursion by runrig (Abbot) on Dec 18, 2006 at 19:58 UTC
Then I was surprised that throwing out all lexicals and directly messing with @_ yields more pleasing results: Except that it has the unpleasant side effect of modifying the caller's argument list :-)	[reply]


Keep It Simple, Stupid
	PerlMonks