Insights Recursion in Programming and When to Use or Not to Use It

[pbuk]

so many algorithms can be implemented as loops instead of recursively

TL;DR ANY algorithm can be implemented with either loops or recursive function calls, so (unless and until you identify that the implementation is too expensive in time or memory) use whichever you find easier to code and therefore more reliable and easier to maintain.

Details

• ANY algorithm can be implemented with loops instead of recursive function calls, however some are easier to implement recursively (e.g. quicksort). Which runs faster and/or with less memory depends on a number of factors.
• ANY algorithm can be implemented with recursive function calls instead of loops, however some are easier to implement with loops (e.g. Fibonacci numbers). Algorithms that are easier to implement with loops run faster and/or with less memory unless the recursion can be performed with exclusively tail calls and the compiler is designed (and set) to optimize very aggressively.
• SOME algorithms cannot be implemented with exclusively tail call recursion. These are often easier to implement recursively because iterative implementation requires the programmer to maintain one or more stacks: again quicksort is a good example, and again which (if either) runs faster and/or with less memory depends on a number of factors.

 

[PeterDonis]

ANY algorithm can be implemented with either loops or recursive function calls

Yes, I was being imprecise; by "loop" I meant a loop that does not have to add more information to some data structure on every iteration; it can update information on every iteration, but only if it throws away the old information so the total information kept track of is of (roughly) constant size.

An example in Python would be a for loop using the range built-in iterator; this does not compute all of the numbers to be iterated over in advance, it only computes them one at a time as they are needed, and throws away the old one each time it computes a new one.

You could of course implement something similar using recursion, as long as whatever language you were using could optimize away the parts that would require storing more data on each iteration (for example, tail call optimization to eliminate repeated pushing of parameters on the stack).

 

[bhobba]

TANY algorithm can be implemented with loops instead of recursive function calls, however some are easier to implement recursively (e.g. quicksort). Which runs faster and/or with less memory depends on a number of factors.

Yes. But it's the whole structured programming thing we had constantly drummed into us during my university days. The choice is made on which will be the most maintainable. Deciding that of course is both art and science. The last time I posted about it on another forum frequented by more modern programmers than me the response I got was - Give me that old-time religion .

Thanks
Bill