140

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

Shivan Dragon
  • 4,583
  • 5
  • 24
  • 31
  • 5
    [You might want to read this](http://blog.javascriptroom.com/2013/01/10/fibonacci-an-introduction-to-recursion/) – Naftali Jan 11 '13 at 14:04
  • 83
    On the subject of recursion, [this](http://programmers.stackexchange.com/questions/182314/recursion-or-while-loops) looks quite interesting. – dan_waterworth Jan 11 '13 at 14:30
  • 4
    @dan_waterworth also, this would help: https://www.google.fr/#hl=en&tbo=d&spell=1&q=recursion&sa=X&ei=MCbwUJmxEOiU0QXG-YG4CA&ved=0CCgQBSgA&bav=on.2,or.r_gc.r_pw.r_qf.&bvm=bv.1357700187,d.d2k&fp=84a3b48c80fa3a9c&biw=1680&bih=925 but I always seem to miss-spell it :P – Shivan Dragon Jan 11 '13 at 14:48
  • @ShivanDragon I thought so ^_^ Very appropriate that I posted it yesterday :-) – Naftali Jan 11 '13 at 15:09
  • Self similar logic and self referencing context is just _more elegant (or may I say natural)_ with recursion, like a mathematical function used in its own definition. Though that does not mean recursion is answer to everything. – S.D. Jan 12 '13 at 15:27
  • Why do you think the stack is smaller? Stack + Heap = Constant or the stack can be in the heap. Why is doing a function call sub-optimal in comparison to doing a loop and manually stacking variables. I would think the cost would be about the same. I believe both those assumptions are wrong (or need to be validated on a machine by machine basis). – Martin York Jan 13 '13 at 21:32
  • @LokiAstari: yes, you're right, both those things I've said are not true in all circumstances (I get that now). However, for certain languages+compilers they are true, for example C and Java have a lot less memory on the stack than they do on the heap, namely, doing a X times recursion can run outta stack memory while re-writing that code as a X-times looping iterative construct will work fine. Also, I am to understand that for languages/compilers that don't do tail call optimization function recursion translates into less optimal machine code than an iterative loop. – Shivan Dragon Jan 14 '13 at 08:35
  • Fibonnaci is not a good example, you can solve the recurrence relation F(n), so no need of recursion nor while loop. – toasted_flakes Jan 15 '13 at 21:12
  • 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. – Fred Thomsen Jan 18 '13 at 00:16
  • @FredThomsen, I know what you mean, I've had the same experience, that's why I asked the question. One the one hand you hear this general (and mostly un-backed) opinion that recursion is horrible, but on the other it pops up a lot at interviews, and in various technical books. At any rate, what I got from the nice people who answered me is that while recursion is in fact pretty evil in certain languages, in others (especially functional ones that support tail call optimization) not only is it preferred but in some cases it's the only way to loop. – Shivan Dragon Jan 18 '13 at 09:31
  • The year is 2013 AD. Tail call and tail recursion optimization are routine for compilers these days. Even compilers for TINY machines (PIC, AVR) do tail call optimization. The PowerPC compiler I was using at Nortel Networks in 2001 did tail recursion optimization. (I got curious one day, did a simple test program, and looked at the generated code.) – John R. Strohm Apr 17 '13 at 14:18

8 Answers8

207

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.

tdammers
  • 52,406
  • 14
  • 106
  • 154
  • 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. – Shivan Dragon Jan 11 '13 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. – Evan Plaice Jan 11 '13 at 17:47
  • Excellent answer indeed, +1 – Laurent Bourgault-Roy Jan 11 '13 at 17:55
  • 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. – Martin York Jan 13 '13 at 21:37
  • @LokiAstari: Quite a lot of algorithms (especially those typically touched in a programming job interview) don't require the full push/pop mechanism, or can be written to use destructive updates instead of using the stack; also, many compilers do *not* optimize tail recursions. – tdammers Jan 14 '13 at 07:51
  • @tdammers: Yet many do. – Martin York Jan 14 '13 at 17: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 Jan 16 '13 at 03: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 Apr 27 '13 at 18:45
  • @YooMatsuo: I think this is the study: http://www.eis.mdx.ac.uk/research/PhDArea/saeed/ – tdammers Apr 27 '13 at 20:40
  • 1
    "*pure languages like Haskell do not have loop constructs at all*" - not as a syntax element maybe, because repetition is just another kind of abstraction. Still, you can loop without mutable state, and Haskell does have list comprehensions, `map`-`filter`-`foldr`, and many other helpers for looping and traversing all kinds of data structures. – Bergi Jun 03 '14 at 21:26
  • 1
    I really liked your answer, especially this piece: "Translating a simple iterative loop into a recursive version is about the quickest possible way of filtering out the non-programmers" There is nothing more true than that, so much people think themselves programmers just because they learned a language manual. I say that flexibility and understanding of concepts are the keys to detach yourself from any programming language. Only in this way you will learn how to program. – Giacomo Cerquone Oct 10 '15 at 16:20
  • So how do you make the recursive call as last statement in method not let the stack overflow? A special code "architecture"? A certain programming language? Something else? (if it is a possibly endless loop) or is that not what you meant? – LuckyLuke Skywalker Aug 19 '22 at 11:47
  • Dehnadi's test tests variable assignment, not pointers or recursion and it suggests it can tell success rate in an entry level programming course. Please share new sources for your statement or remove you claim about it being based on research. – Jonas Äppelgran Jun 27 '23 at 10:41
38

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

Community
  • 1
jk.
  • 10,216
  • 1
  • 33
  • 43
  • 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 Jan 11 '13 at 10:59
  • 4
    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
  • 5
    @dan_waterworth compared to "100 line" it's rather difficult to be *overly* terse – gnat Jan 11 '13 at 11:13
  • @dan_waterworth: I think sometimes code can to be overly terse because it uses too many idioms of a particular programming language. In that case, only a very experienced programmer can "see" all the implicit information in the code. On the other hand, I think it is not bad if the code is concise because it is constructed by combining a few powerful constructs. – Giorgio Jan 11 '13 at 11:18
  • 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. – dan_waterworth Jan 11 '13 at 11:30
  • @dan_waterworth: I think we mean similar things: programming language idioms can make code shorter because some information is made implicit. If you use this too much your code can become quite cryptic. – Giorgio Jan 11 '13 at 11:36
  • The other form of over terseness you get is when identifiers have been compressed. Generally I think that as long as you are removing some symmetry/repetition in the code it is improrved. – jk. Jan 11 '13 at 11:46
  • 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. – dan_waterworth Jan 11 '13 at 12:22
  • @dan_waterworth thats an interesting interpretation that I hadn't considered before, thanks. – jk. Jan 11 '13 at 13:03
  • @gnat If you think it's difficult for code to be overly terse, then I feel like you have never seen [code golf](http://codegolf.stackexchange.com/). – Peter Olson Jan 11 '13 at 14:50
  • @PeterOlson don't get me wrong I have no problems preferring 10-20 LOC over 5. But **100**... I can only quote self, "compared to this it's rather difficult to be _overly_ terse". Just checked - my 22' widescreen monitor turned portrait shows only 89 lines in my IDE, give me a break – gnat Jan 11 '13 at 15:14
  • @gnat I can think of a more extreme example where 100+ LOC could be preferred over 1 LOC: a reasonable implementation of Conway's game of life could easily take over 100 lines of code in JavaScript, whereas it's been implemented in (a very hard to understand) one line of APL. – Peter Olson Jan 11 '13 at 16:39
  • @PeterOlson sure. That's exactly why I didn't wrote _impossible_: "difficult" is the word – gnat Jan 11 '13 at 16:50
17

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.

dan_waterworth
  • 7,287
  • 2
  • 34
  • 45
  • 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 Jan 11 '13 at 11:10
  • 1
    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
  • "Ideally, you'd use the least expressive constructs that you can." - I had to think about what you mean. My guess is you meant the most abstract one. – Maciej Piechotka Jan 11 '13 at 12:46
  • @Giorgio, oh I see, I thought you were correcting me ;) – dan_waterworth Jan 11 '13 at 12:47
  • @MaciejPiechotka, I mean, if you have a choice between using a powerful construct and a less powerful construct, you should always go for the less powerful option. You shouldn't use continuations when you only need exceptions, for example. – dan_waterworth Jan 11 '13 at 12:54
  • @dan_waterworth: It was more correction about wording. To use example from Haskell - don't use Monads where Functor would do - or from Java/C#/... - don't use ArrayList where List would do. – Maciej Piechotka Jan 11 '13 at 13:02
  • @MaciejPiechotka, I think we agree. I didn't know whether you meant 'abstract' as in least specific or 'abstract' as in least tangible. – dan_waterworth Jan 11 '13 at 13:12
  • What, no mention of `while` loops with immutable data? After all, those are indeed very, very low in expressive power. About as low as you can get, in fact. ;] – C. A. McCann Apr 18 '13 at 14:31
8

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.

SF.
  • 5,078
  • 2
  • 24
  • 36
  • 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 Jan 11 '13 at 11:24
  • 1
    @Giorgio: For WRITING yes, for YOU yes, but what about the person who is to maintain it after you? 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). And now if you call g(x) in f(x), and then f(x-1) inside g(x), and only for the reason you didn't feel like writing a loop and thought to split the recursive function into two, called in sequence? Expect profanities. – SF. Jan 11 '13 at 11:42
  • @SF perhaps this is why it was an interview question. Their existing codebase is full of recursion. They don't want to change. They want to see if the candidate can grok it. – emory Jan 11 '13 at 12:26
  • @SF: What I was trying to say is that most programmers (including me) are more used to iteration because they have used it more often, and that it is used more often because it is more efficient. – Giorgio Jan 11 '13 at 12:40
  • @Giorgio: I would say that it is not more efficient per se but more efficient in very old compilers and in most popular platform (JVM don't have tail recursion optimalization IIRC). – Maciej Piechotka Jan 11 '13 at 12:45
  • 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 Jan 11 '13 at 12:45
  • @Maciej Piechotka: I agree with you that with modern computers and languages using (tail) recursion is comparably efficient to loops. This was not true in the past and probably this is why the imperative (loop-oriented) paradigm has become more popular. – Giorgio Jan 11 '13 at 12:52
  • 1
    @Giorgio: You still talk about writing which takes 10% of the time. I'm talking about maintaining and debugging which is 90% time. If you debug a fragment of a program, and you see a function call, you really need to know whether it's a recursive loop over a whole range or whether the programmer just wants to modify the first element of a list/table/string and leave the rest untouched. – SF. Jan 11 '13 at 13:03
  • 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 Jan 11 '13 at 13:16
  • @Giorgio: In case of loop placed outside the function, calling it for each element, I don't need to look at the function body. `char a[]="hello world; toUpperCase(a);` - does it uppercase whole string or just its first character? I must open the function body. If I see `char a[]="hello world; for(char *b = a; *b != '\0';b++){ toUpperCase(b); }` I have no doubts. – SF. Jan 11 '13 at 13:25
  • What about `let a = map toUpper "hello world"`? Anyone familiar with this language can see that `toUpper` is applied to each character of the string `"hello world"`. – Giorgio Jan 11 '13 at 13:38
  • @Giorgio: `map` is still a loop ("foreach") keyword from the user's viewpoint, making it obvious toUpper works on a single element. (how compiler realizes it is besides the point) – SF. Jan 11 '13 at 13:45
  • 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. http://www.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
  • 1
    @Giorgio: If it quacks like a duck? Using `map` you're using a system keyword that *iterates* [dictionary meaning] over all elements of a list. A loop based on `Label:... if(condition) goto Label` is non-obvious too for the same reason as recursion is non-obvious - but nobody does it nowadays. – SF. Jan 11 '13 at 14:25
  • 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. – dan_waterworth Jan 11 '13 at 19:52
  • 3
    Essentially, it's not about what a function does, it's about what it means. – dan_waterworth Jan 11 '13 at 19:59
  • @dan_waterworth: This is all again about writing. While writing you happily accept what the function means and enjoy the simplicity, assuming the function is correct. Debugging is all about "what the function actually does, versus what it was supposed to do", and all the elegance and simplicity of writing crashes on your head. "Dirty mechanics" which recursion manages to hide efficiently is where usually the problem lies, and debugging stuff that happens behind the scenes is always harder than debugging what lies out in the open. – SF. Jul 06 '14 at 09:30
6

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.
Kilian Foth
  • 107,706
  • 45
  • 295
  • 310
  • 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
1

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.

Peter Mortensen
  • 1,050
  • 2
  • 12
  • 14
neotam
  • 119
  • 2
  • 3
    [Here](http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html) 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
1

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

Martijn Pieters
  • 14,499
  • 10
  • 57
  • 58
okobaka
  • 137
  • 1
-1

Use the strategy design pattern.

  • Recursion is clean
  • Loops are (arguably) efficient

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

Pravin Sonawane
  • 157
  • 3
  • 6
    Wait, what? How does the strategy pattern fit in here? And the second sentence sounds like an empty phrase. – Konrad Rudolph Jan 11 '13 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. – Pravin Sonawane Jan 11 '13 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. – Konrad Rudolph Jan 11 '13 at 11:20
  • @KonradRudolph learnt an important lesson. Deeply explain what you want to say.. Thanks.. that helped.. :) – Pravin Sonawane Jan 11 '13 at 11:25
  • 2
    @Pravin Sonawane: If you can use tail recursion optimization you can use recursion also on huge data sets. – Giorgio Jan 11 '13 at 11:28