Re: recursion to iteration macro

[Philip Kaludercic <philipk@posteo.net>]

Emanuel Berg <incal@dataswamp.org> writes:

> Did anyone try to write a macro or by using some other method
> to translate arbitrary use of recursion into functionally
> equivalent code that is iteration only?
>
> I read [1] this is theoretically possible and that seems
> reasonable as well, as with loops, local functions etc you
> have everything you need to implement it.

At least for tail-call recursion, named-let will turn recursive code
into iterative code.

But generally speaking, if you need to accumulate data on the stack,
then it becomes a lot more difficult.

> You can even have an expanding data structure, e.g. a list, to
> implement a virtual stack, still all within the one function,
> if you are fond of it.
>
> With execution all advantages should be with iteration but
> sometimes recursion makes for compact, elegant code that can
> also be more intuitive, more fun to write.
>
> Recursion is not so common, in part for this exact reason, but
> if we had this, maybe we would see a little recursion
> renaissance and proliferation?
>
> The best of both worlds anyone? You _will_ be assimilated!
>
> [1] https://en.wikipedia.org/wiki/Recursion_(computer_science)
>     https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration

-- 
	Philip Kaludercic on peregrine