Recursion or while loops

Question

I was reading about some development interview practices, specifically about the technical questions and tests asked at interviews and I've stumbled quite a few times over sayings of the genre "Ok you solved the problem with a while loop, now can you do it with recursion", or "everyone can solve this with a 100 lines while loop, but can they do it in a 5 lines recursive function?" etc.

My question is, is recursion generally better than if/while/for constructs?

I've honestly always thought that recursion is not to be preferred, because it's limited to the stack memory which is a lot smaller than the heap, also doing a great number of function/method calls is suboptimal from a performance standpoint, but I may be wrong...

Answer 1

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. OTOH, 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 idiosyncracies.

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.

Answer 2

It depends.

• 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).

Answer 3

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.

Answer 4

Recursion is often less obvious. Less obvious is harder to maintain.

If you write for(i=0;i<ITER_LIMIT;i++){somefunction(i);} in the main flow, you make it perfectly clear you are writing a loop. If you write somefunction(ITER_LIMIT); you don't really make it clear what will happen. Only seeing content: that somefunction(int x) calls somefunction(x-1) tells you it is in fact a loop using iterations. Also, you can't easily put an escape condition with break; somewhere halfway the iterations, you must either add a conditional that will be passed all the way back, or throw an exception. (and exceptions again add complexity...)

In essence, if it's an obvious choice between iteration and recursion, do the intuitive thing. If iteration does the job easily, saving 2 lines is rarely worth the headaches it may create in the long run.

Of course if it's saving you 98 lines, that's an entirely different matter.

There are situations for which recursion simply fits perfectly, and they aren't really uncommon. Traversal of tree structures, multiply-linked networks, structures that can contain its own type, multi-dimensional jagged arrays, essentially anything that isn't either a straightforward vector or an array of fixed dimensions. If you traverse a known, straight path, iterate. If you dive into unknown, recurse.

Essentially, if somefunction(x-1) is to be called from within itself more than once per level, forget iterations.

...Writing iteratively functions for tasks that are best done by recursion is possible but not pleasant. Wherever you'd use int, you need something like stack<int>. I did it once, more as an exercise than for practical purposes. I can assure you once you face such a task you won't have doubts like the ones you expressed.

Answer 5

As usual, this is unanswerable in general because there are additional factors, which in practice are widely unequal between cases and unequal to each other within a use case. Here are some of the pressures.

• Short, elegant code is in general superior to long, intricate code.
• However, the last point is somewhat invalidated if your developer base is not familiar with recursion and unwilling/unable to learn. It may even become a slight negative rather than a positive.
• Recursion can be bad for efficiency if you will need deeply-nested calls in practice and you can't use tail recursion (or your environment can't optimize tail recursion).
• Recursion is also bad in many cases if you can't properly cache intermediate results. For instance, the common example of using tree recursion to compute Fibonacci numbers performs horribly bad if you don't cache. If you do cache, it's simple, fast, elegant and altogether wonderful.
• Recursion is not applicable to some cases, just as good as iteration in others, and absolutely necessary in yet others. Plodding through long chains of business rules is usually not helped by recursion at all. Iterating through data streams can be usefully done with recursion. Iterating over multidimensional dynamic data structures (e.g. mazes, object trees...) is pretty much impossible without recursion, explicit or implicit. Note that in these cases, explicit recursion is much better than implicit - nothing is more painful than reading code where somebody implemented their own ad-hoc, incomplete, buggy stack within the language just to avoid the scary R-word.

Answer 6

Recursion is about repeating call to function, loop is about repeating jump to place in memory.

Should be mentioned also about stack overflow - http://en.wikipedia.org/wiki/Stack_overflow

Answer 7

It really depends on convenience or the requirement:

If you take the programming language Python, it supports recursion, but by default there is a limit for the recursion depth (1000). If it exceeds the limit, we will get an error or exception. That limit can be changed, but if we do that we may experience abnormal situations in the language.

At this time (number of calls more than recursion depth), we need to prefer loop constructs. I mean, if the stack size is not enough, we have to prefer the loop constructs.

Answer 8

Use the strategy design pattern.

• Recursion is clean
• Loops are (arguably) efficient

Depending on your load (and/or other conditions), choose one.