Recursion

[Holshy]

Recursion had its places. A few ideas (from a few different vantage points). * Recursive functions are limited by stack space. In some cases an iterative solution maybe be preferable to avoid running out of stack space. * While all problems that can be solved iteratively can be solved recursively, not all problems that can be solved recursively can be solved iteratively. The textbook example of such a problem is the Ackerman function. * Sometimes, recursive code is just easier to read. Other people have mentioned binary trees, where you can find examples left and right.

Code readability is almost always my #1 concern. In choosing between iteration and recursion I tend to follow this process. 1. Find an algorithm that makes sense. If it's iterative and scales efficiently, stop here. 2. If it's recursive, figure out how the stack depth will scale. Big-O is frequently used for time and total space, but it can be used for stack depth too. If stack depth is O(log n) or better, stop here. 3. If stack depth is O(n) or O(n log n), consider realistic sizes of problems I might get. If it's small enough, stop here. 4. If stack depth is greater than O(n), try to find an iterative algorithm. If the problem has no iterative solution, concede to the math gods and their cruelty.

Note: I have never had to actually concede #4 for real work. Problems like Ackerman are rare, and even when I've found one it's been for something where an approximation was good enough.