# Recursion or while loops

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

-
You might want to read this – Neal Jan 11 '13 at 14:04
On the subject of recursion, this looks quite interesting. – dan_waterworth Jan 11 '13 at 14:30
@dan_waterworth also, this would help: google.fr/… but I always seem to miss-spell it :P – Shivan Dragon Jan 11 '13 at 14:48
@Neal thanks, that's actually very helpful. – Shivan Dragon Jan 11 '13 at 15:04
In the embedded environments I've worked in recursion is frowned upon at best and gets you publicly flogged at worst. The limited stack space in effect makes it illegal. – Fred Thomsen Jan 18 '13 at 0:16

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.

-
I like your answer best,because it touches on most important aspects that an answer to this question could have, it explains the main technical parts,and it also gives a good zoomed-out view on how this issue fits in the programming sphere. – Shivan Dragon Jan 11 '13 at 13:33
I have also noticed a pattern in a sync programming where loops are avoided in favor of recursive calls on an iterator that contains a .next() method. I assume it keeps long running code from becoming too CPU greedy. – Evan Plaice Jan 11 '13 at 17:47
The iterative version also involves pushing and poping values. You just have to manually write the code to do this. The recursive version is pushing state onto the stack in an iterative algorithm you usually have to manually simulate this by pushing state into a some structure. Only the most trivial algorithms don't need this state and in these cases the compiler can usually spot the tail recursion and plant an iterative solution. – Loki Astari Jan 13 '13 at 21:37
@tdammers Could you tell me where I can read the study you mentioned "Experience and research suggest that there is a line between people..." This seems to be very interesting for me. – Yoo Matsuo Jan 16 '13 at 3:10
One thing you forgot to mention, iterative code tends to perform better when you're dealing with a single thread of execution, but recursive algorithms tend to lend themselves to being executed in multiple threads. – GordonM Apr 27 '13 at 18:45

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

-
Nice answer (+1). "a 5 line solution is probably always better than a 100 line one": I think conciseness is not the only advantage of recursion. Using a recursive call forces you to make the functional dependencies between values in different iterations explicit. – Giorgio Jan 11 '13 at 10:59
Shorter solutions do tend to be better, but there is such a thing as being overly terse. – dan_waterworth Jan 11 '13 at 11:08
@dan_waterworth compared to "100 line" it's rather difficult to be overly terse – gnat Jan 11 '13 at 11:13
@Giorgio, You can make programs smaller by removing unnecessary code or by making explicit things implicit. So long as you stick to the former, you improve the quality. – dan_waterworth Jan 11 '13 at 11:30
@jk, I think that's another form of making explicit information implicit. The information about what a variable is used for is removed from its name where it is explicit and is pushed into it's usage which is implicit. – dan_waterworth Jan 11 '13 at 12:22

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.

-
"a while loop is equivalent to a tail recursive function and recursive functions need not be tail recursive": +1. You can simulate recursion by means of a while loop + a stack. – Giorgio Jan 11 '13 at 11:10
I’m not sure I agree 100% but it’s certainly an interesting perspective so +1 for that. – Konrad Rudolph Jan 11 '13 at 11:12
+1 for a great answer and also for mentioning that some languages (or compilers) don't do tail call optimizations. – Shivan Dragon Jan 11 '13 at 11:22
@Giorgio, "You can simulate recursion by means of a while loop + a stack", This is why I said expressive power. Computationally, they are equally powerful. – dan_waterworth Jan 11 '13 at 12:19
@dan_waterworth: Exactly, and as you said in your answer, recursion alone is more expressive than a while loop because you need to add a stack to a while loop to simulate recursion. – Giorgio Jan 11 '13 at 12:42

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.
-
What do you mean by caching in relation to recursion? – Giorgio Jan 11 '13 at 11:07
@Giorgio presumably memoization – jk. Jan 11 '13 at 11:38
Feh. If your environment doesn't optimize tail calls you should find a better environment, and if your developers are unfamiliar with recursion you should find better developers. Have some standards, people! – C. A. McCann Apr 18 '13 at 14:35

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.

-
What is obvious and what is less obvious depends partially on what you are used to. Iteration has been used more often in programming languages because it is closer to the CPU's way of working (i.e. it is uses less memory and executes faster). But if you are used to thinking inductively, recursion can be as intuitive. – Giorgio Jan 11 '13 at 11:24
"If they see a loop keyword, they know it's a loop. But there is no recurse keyword, they can recognize it only by seeing f(x-1) inside f(x).": When you call a recursive function you do not want to know that it is recursive. Similarly, when you call a function containing a loop, you do not want to know that it contains a loop. – Giorgio Jan 11 '13 at 12:45
@SF: Yes but you can only see this if you look at the body of the function. In case of a loop, you see the loop, in case of recursion, you see that the function calls itself. – Giorgio Jan 11 '13 at 13:16
@SF: Seems a bit like circular reasoning to me: "If in my intuition it is a loop, then it is a a loop." `map` can be defined as a recursive function (see e.g. haskell.org/tutorial/functions.html), even if it is intuitively clear that it traverses a list and applies a function to each member of the list. – Giorgio Jan 11 '13 at 14:08
@SF, `map` is not a keyword, it's a regular function, but that's a little irrelevant. When functional programmers use recursion, it's usually not because they want to perform a sequence of actions, it's because the problem being solved can be expressed as a function and a list of arguments. The problem can then reduced to another function and another list of arguments. Eventually, you have a problem that can be solved trivially. – dan_waterworth Jan 11 '13 at 19:52

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

-
Recursion means a function whose definition entails calling itself. – hardmath Jan 14 '13 at 19:57
While your simple definition isn't exactly 100% accurate, you're the only one that mentioned stack overflows. – Qix Jan 24 '13 at 8:56

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.

-
Here is a blog by Guido van Rossum as to why he doesn't want tail-recursion optimization in Python (supporting the notion that different languages take distinct tactical approaches). – hardmath Jan 11 '13 at 16:30

Use the strategy design pattern.

• Recursion is clean
• Loops are (arguably) efficient