Recursion

by Karel Thönissen

In Joel on Software people argued about the pros and cons of recursion. Although some interesting objections were brought forward, I am again astonished by the shortness of the intellectual horizon of many practitioners in our discipline. I contributed:

How do you keep your data in an iterative design? You put it in objects on the heap. No matter how you put it, you have just invented the stack as an abstract data type. This should be a bad thing, because you are reinventing the wheel. However, often your heap is larger than the available stack space.

If that is the case, that is a clear indication of another problem: wrong programming language for this recursive idiom. There are plenty of languages that do not have this limitation: some of them put the activation records on the heap (some implementations of Lisp and Small-talk) or they allow tail recursion. Ideally, you have both.

Many posters made valid remarks about the limitations of recursion, but they forgot to mention that this is not a limitation of recursion per se, but of the tool they use.