This article was posted originally on Arstechnica.
It’s a question young programmers confront often.
It’s a response often encountered during technical interviews: “OK, you solved the problem with a while loop, now do it with recursion.” Or vice versa. Stack Exchange user Shivan Dragon has encountered the problem and he knows how to answer: show that you’re able to code both ways. Give the interviewer what he wants. But which method is generally preferable? A few more experienced programmers respond.
See the original question here.
What’s the problem that needs to be solved?
- Some problems are very amenable to recursive solutions e.g. quicksort
- Some languages don’t really support recursion e.g. early FORTRANs
- Some languages assume recursion as a primary means for looping e.g. Haskell
It’s also worth noting that support for tail recursion makes tail recursive and iterative loops equivalent, that is, recursion doesn’t always have to waste the stack.
Also, a recursive algorithm can always be implemented iteratively by using an explicit stack.
Finally, I’d note that a five-line solution is probably always better than a 100 line one (assuming they are actually equivalent).
Expression is key
There’s no universally agreed on definition of “better” when it comes to programming, but I’ll take it to mean “easier to maintain/read.”
Recursion has more expressive power than iterative looping constructs. I say this because a while loop is equivalent to a tail recursive function and recursive functions need not be tail recursive. Powerful constructs are usually a bad thing because they allow you to do things that are difficult to read. However, recursion gives you the ability to write loops without using mutability, and to my mind mutability is much more powerful than recursion.
So, from low expressive power to high expressive power, looping constructs stack up like this:
- Tail recursive functions that use immutable data
- Recursive functions that use immutable data
- While loops that use mutable data
- Tail recursive functions that use mutable data
- Recursive functions that use mutable data
Ideally, you’d use the least expressive constructs that you can. Of course, if your language doesn’t support tail call optimization, then that may also influence your choice of looping construct.
Recursion is not intrinsically better or worse than loops—each has advantages and disadvantages, and those even depend on the programming language (and implementation).
Technically, iterative loops fit typical computer systems better at the hardware level: at the machine code level, a loop is just a test and a conditional jump, whereas recursion (implemented naively) involves pushing a stack frame, jumping, returning, and popping back from the stack. On the other hand, many cases of recursion (especially those that are trivially equivalent to iterative loops) can be written so that the stack push / pop can be avoided. This is possible when the recursive function call is the last thing that happens in the function body before returning, and it’s commonly known as a tail call optimization (or tail recursion optimization). A properly tail-call-optimized recursive function is mostly equivalent to an iterative loop at the machine code level.
Another consideration is that iterative loops require destructive state updates, which makes them incompatible with pure (side-effect free) language semantics. This is the reason why pure languages like Haskell do not have loop constructs at all, and many other functional-programming languages either lack them completely or avoid them as much as possible.
The reason why these questions appear so much in interviews, though, is because in order to answer them, you need a thorough understanding of many vital programming concepts—variables, function calls, scope, and of course loops and recursion—and you have to bring the mental flexibility to the table that allows you to approach a problem from two radically different angles, and move between different manifestations of the same concept.
Experience and research suggest that there is a line between people who have the ability to understand variables, pointers, and recursion, and those who don’t. Almost everything else in programming, including frameworks, APIs, programming languages and their edge cases, can be acquired through studying and experience, but if you are unable to develop an intuition for these three core concepts, you are unfit to be a programmer. Translating a simple iterative loop into a recursive version is about the quickest possible way of filtering out the non-programmers—even a rather inexperienced programmer can usually do it in 15 minutes, and it’s a very language-agnostic problem, so the candidate can pick a language of their choice instead of stumbling over idiosyncrasies.
If you get a question like this in an interview, that’s a good sign: it means the prospective employer is looking for people who can program, not people who have memorized a programming tool’s manual.
Find more answers or leave your own at the original post. See more Q&A like this at Programmers, a site for conceptual programming questions at Stack Exchange. And of course, feel free to login and ask your own.