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

  • 5
    You might want to read this
    – Naftali
    Commented Jan 11, 2013 at 14:04
  • 84
    On the subject of recursion, this looks quite interesting. Commented Jan 11, 2013 at 14:30
  • 4
    @dan_waterworth also, this would help: google.fr/… but I always seem to miss-spell it :P Commented Jan 11, 2013 at 14:48
  • @ShivanDragon I thought so ^_^ Very appropriate that I posted it yesterday :-)
    – Naftali
    Commented Jan 11, 2013 at 15:09
  • 2
    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. Commented Jan 18, 2013 at 0:16

8 Answers 8


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.

  • 4
    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. Commented Jan 11, 2013 at 13:33
  • 1
    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. Commented Jan 11, 2013 at 17:47
  • 1
    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. Commented Jan 13, 2013 at 21:37
  • 1
    @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
    Commented Jan 16, 2013 at 3:10
  • 2
    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
    Commented Apr 27, 2013 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).

  • 5
    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
    Commented Jan 11, 2013 at 10:59
  • 4
    Shorter solutions do tend to be better, but there is such a thing as being overly terse. Commented Jan 11, 2013 at 11:08
  • 5
    @dan_waterworth compared to "100 line" it's rather difficult to be overly terse
    – gnat
    Commented Jan 11, 2013 at 11:13
  • 4
    @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. Commented Jan 11, 2013 at 11:30
  • 1
    @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. Commented Jan 11, 2013 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.

  • 1
    "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
    Commented Jan 11, 2013 at 11:10
  • 1
    I’m not sure I agree 100% but it’s certainly an interesting perspective so +1 for that. Commented Jan 11, 2013 at 11:12
  • +1 for a great answer and also for mentioning that some languages (or compilers) don't do tail call optimizations. Commented Jan 11, 2013 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. Commented Jan 11, 2013 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
    Commented Jan 11, 2013 at 12:42

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.

  • 10
    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
    Commented Jan 11, 2013 at 11:24
  • 6
    "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
    Commented Jan 11, 2013 at 12:45
  • 4
    @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
    Commented Jan 11, 2013 at 13:16
  • 6
    @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
    Commented Jan 11, 2013 at 14:08
  • 5
    @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. Commented Jan 11, 2013 at 19:52

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
    Commented Jan 11, 2013 at 11:07
  • @Giorgio presumably memoization
    – jk.
    Commented Jan 11, 2013 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! Commented Apr 18, 2013 at 14:35

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

  • 1
    Recursion means a function whose definition entails calling itself.
    – hardmath
    Commented Jan 14, 2013 at 19:57
  • 1
    While your simple definition isn't exactly 100% accurate, you're the only one that mentioned stack overflows. Commented Jan 24, 2013 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.

  • 3
    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
    Commented Jan 11, 2013 at 16:30

Use the strategy design pattern.

  • Recursion is clean
  • Loops are (arguably) efficient

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

  • 6
    Wait, what? How does the strategy pattern fit in here? And the second sentence sounds like an empty phrase. Commented Jan 11, 2013 at 11:11
  • @KonradRudolph I would go for recursion. For very large sets of data, I would switch to loops. That's what I meant. I apologize if it wasn't clear. Commented Jan 11, 2013 at 11:16
  • 3
    Ah. Well, I’m still not sure that this can be called “strategy design pattern”, which has a very fixed meaning and you use it metaphorical. But now at least I see where you’re going. Commented Jan 11, 2013 at 11:20
  • @KonradRudolph learnt an important lesson. Deeply explain what you want to say.. Thanks.. that helped.. :) Commented Jan 11, 2013 at 11:25
  • 2
    @Pravin Sonawane: If you can use tail recursion optimization you can use recursion also on huge data sets.
    – Giorgio
    Commented Jan 11, 2013 at 11:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.