Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

(tye)Re: Recursion

by tye (Sage)
on Nov 15, 2000 at 00:57 UTC ( [id://41646] : note . print w/replies, xml ) Need Help??

in reply to (jeffa) Re: Recursion
in thread Recursion

"Implementing your own stack" is trivial in Perl. I think this argument applies more to C where you don't already have efficient, self-growing lists handy.

If you may need to recurse very deeply, then you may be better off implementing your own stack since it will likely be more compact.

As for the original question of which works better in Perl... I think Perl supports both quite well, better than many languages (like making it trivial to implement your own stack).

Here are what I see as the main trade-offs. Recursion is usually easier to write correctly the first time. Looping is usually more efficient in space and time (ie. faster and uses less memory). Recursion makes it hard to be flexible in the interface you provide -- you either return a big list or make the user provide call-backs. Looping lets you provide iterators.

So it is often best to start with a recursive method. Later, if you need more speed or less memory consumption, then you can do the extra work to switch to looping. Also, if you provide your code for others to use (for example, by creating a module), then you might want to do the extra work to switch to looping and provide a more flexible interface (and more efficiency).

But if you know you plan to make this available to others or suspect that efficiency will be unusually important here, then you may want to analyze how you'd solve the problem without recursion to see if you want to start off that way and avoid having to convert later.

Also, by allowing an "iterator" interface, "looping" may allow you to deal with problems that are too big to deal with (naively) recursively. For example, finding all permutations is very quick to code recusively. But most such will just return a list of all permutations. It is trivial to feed a rather small list to these routines and exhaust memory. A non-recursive routine would likely allow you to repeatedly request the "next permutation" so you could eventually "deal with" them all without having to try to store them all.

You could "fix" such a recursive routine by teaching it to call a user call-back function for each permutation found. But this just forces users of your code into an often-inconvenient method of coding. Better to spend that effort making your code non-recursive with an interator interface.

        - tye (but my friends call me "Tye")