Even before I learned Lisp, I really loved coding with recursive algorithms. When I decided to learn Lisp, I did so through Paul Graham’s ANSI Common Lisp, which meant, of course, that recursive programming became part of my programming DNA.
A significant part of my Lisp journey involved Scheme where recursion is the go to mechanism for most looping constructs. That’s because the Scheme standard mandates tail call optimization so that recursion is no more expensive in time or memory than any other looping mechanism. Not all languages or even all compilers for a given language support tail call optimization so a prejudice against recursion has emerged. The problem, according to this prejudice, is that recursion can lead to stack space exhaustion.
Tim Bradshaw examines this prejudice and dismisses it for the silliness it is. According to Bradshaw, there’s a deep-seated belief among programmers that stack space is a scarce, valuable resource while heap space is essentially free and unlimited. This leads to a preference for implementing inherently recursive procedures in an interactive way that involves managing the stack explicitly in the heap rather than using recursion and managing the stack implicitly.
As Bradshaw points out, the stack and the heap are both just memory and neither is more expensive or scarce than the other. There’s no reason to restrict stack space while allowing large heap spaces other than convention and it’s time for us to reexamine this prejudice. It’s hard to argue; Bradshaw has a point.