Recursion - when would you use it and when wouldn't you use it?
+2
A:
I would use it when it made a problem easier and I had a large amount of stack memory (in case of a large stack).
I wouldn't use it if stack memory was at a premium (so the call stack doesn't grow too large and cause the stack to overflow and your application to fail).
Justin Niessner
2010-07-06 16:15:36
See also [When do you worry about stack size?](http://stackoverflow.com/questions/1915900)
ChrisW
2010-07-06 16:20:03
I would clarify that it's specifically **stack** memory you're talking about here, not memory in general. And even that may not make a difference if you're doing tail calls and you're running on a recent CLR.
Daniel Pryden
2010-07-06 16:20:56
True and I'll give you an upvote, but possibly unhelpful in that you don't say when it makes the problem easier. Also, the problem with deep recursion is not generally that the stack grows too large and causes performance issues, but that the stack overflows and the program fails.
Jay
2010-07-06 16:40:14
@incrediman I downvoted it because I thought it was a tired joke, unhelpful at best (and at worst, offensive to the OP).
ChrisW
2010-07-06 16:23:23
@Jesse: I did. The base case is when I don't have a problem that requires recursion.
Daniel Pryden
2010-07-06 16:24:55
@ChrisW: The links may be in jest, but I think the text of my answer is a completely appropriate and accurate answer to the question.
Daniel Pryden
2010-07-06 16:27:37
My guess is the downvotes are because it's a joke that's been done before and it doesn't address the actual performance concerns behind using recursion.
Justin Niessner
2010-07-06 16:29:55
I didn't take this is a flippant answer at all. It is an appropriately general answer to an impossibly general question.
Adam Crossland
2010-07-06 16:30:41
@Justin: There are only performance concerns if (a) you are using recursion where it's unnecessary, and (b) you don't have tail-call optimization. There are performance concerns with using loops as well (e.g. branch misprediction), but that doesn't mean you shouldn't use them.
Daniel Pryden
2010-07-06 16:31:39
I think that this sort of thing (more than a simple joke to me), if you are wise and meditate on it enough, can be enlightening, in general, also to the OP. So +1
ShinTakezou
2010-07-06 16:32:42
@Niessner there are performance concerns? The OP does not specify that the focus is on performance. I would say that many algorithms can be expressed naturally, easily, more clearly and swiftly using recursion. This can be a good point to use it, if you are not interested in performance. - BTW smart usage of recursion can be performant (see other answer talking about memoization e.g.): I've just solved many puzzles on projecteuler using recursion and memoization and taking less than one second.
ShinTakezou
2010-07-06 16:34:49
It's a slick answer, but it presupposes knowing when to use recursion, and it therefore adds to little to nothing, IMO: "I use it when I need to." Well, duh, of course you do.
ChrisW
2010-07-06 16:36:32
The joke isn't merely tired, it's **fossilized**. *Everyone* thinks of this joke at some point. You can take it as a given that Ada thought of this joke and was simply to genteel to commit it to paper.
dmckee
2010-07-06 16:36:54
@ShinTakezou @Daniel - The performance concerns I was referring to don't necessarily apply to most machines. They would apply when you're working with something that has a limited stack size like embedded systems (possible with the C# Micro Framework). Even situations that lend themselves to properly optimized recursion can cause problems.
Justin Niessner
2010-07-06 16:41:53
@Adam - They're still recursive and still fill the call stack. On something with a small call stack, your program will overflow and fail. Poor wording on my part to call that a performance issue though.
Justin Niessner
2010-07-06 16:49:26
@Justin -- that's the whole point of proper tail calls; they do not use any extra stack space: http://en.wikipedia.org/wiki/Tail_recursion
Adam Crossland
2010-07-06 16:52:40
@Niessner I agree,but I don't see if the OP is interested in that,or if s/he's asking a more general Q,even though related to C# (by tag,otherwise I would say it is lang-agnostic).Exhausting the stack is [more than a perf problem](http://rosettacode.org/wiki/Find_limit_of_recursion);indeed,it shouldn't affect too much performance _per se_,what eats cycles is the calling of a function in general,not in particular the calling of the same function:a loop calling 100 times a func could be comparable in performance to recursing 100 times ("lr"-like calling technics is a little perfboost if ...)
ShinTakezou
2010-07-06 16:56:55
@Adam - Does C# require the use of Trampolining to actually keep from growing the call stack (sounds like an interesting IL exercise)?
Justin Niessner
2010-07-06 16:59:02
@Niessner read your comment on poor wording now:) anyway I have not met yet a language or whatever that does not incur in a stack exhaustion. Even with tail recursion. Since it does not use extra stack space, but somewhere it is used anyway, tail recursion just push the recursion limit further. An iterative equivalent algorithm can reach other limits, but not that limit.
ShinTakezou
2010-07-06 17:01:43
@Justin: It's possible that the Microsoft CLR implementation uses a trampoline. But the `tail.` instruction is built into MSIL, so it's not something that's special-cased for C# (in fact, F# uses it much more heavily). See: http://msdn.microsoft.com/en-us/library/system.reflection.emit.opcodes.tailcall.aspx
Daniel Pryden
2010-07-06 18:16:51
@ShinTakezou: With tail-call optimization in place, many naively recursive functions can be transformed from O(n) to O(1) stack storage, so there is no storage being used "somewhere" instead. Of course, any tail-recursive function that uses O(1) storage can be transformed into an iterative function anyway (and in fact that's exactly what tail-call optimization does).
Daniel Pryden
2010-07-06 18:18:59
@Pryden so, tail-recursion is the case when it is easy to do it iteratively, and the transformation is done automatically. So we are not into recursion at all, but formally. If you take a look at the link I've given, you can see all tail-recursion recursive function. None I can test directly iterates forever. I don't know why, where or when but somewhere stack is always consumed, => no optimization of the tail-recursion is done; in this case: how could we make it so that it is done for sure? Which version of C#... and what about Mono?
ShinTakezou
2010-07-06 20:32:57
@ShinTakezou: You might want to check out this question: http://stackoverflow.com/questions/491376/why-doesnt-net-c-eliminate-tail-recursion
Daniel Pryden
2010-07-06 21:22:34
I didn't vote, but this is an old joke even in SO. It used to be funny.
Amarghosh
2010-07-07 06:52:19
+2
A:
Very language dependent. Be very careful with languages like Ruby that don't have very good tail call optimization. True functional languages handle recursion better. Make sure you know about memoization before you start to rely on it too much. Where I really use it is when I know the full bounds of the inputs and outputs. If I know I won't ever, ever, go 100 levels deep then I'll use it (in Ruby, at least), otherwise I find a different pattern. I wish recursion was faster, because so often I find a really neat 2 line solution that I love, but that doesn't preform stably or quickly so I'll have to replace it.
zachaysan
2010-07-06 16:19:43
A:
I would use it if, and only if, it was obviously the correct solution and no other method could possibly be correct.
Perhaps for a factorial function, although probably not. Try the Fibonnaci sequence
f(n) = f(n - 1) + f(n - 2), f(0) = f(1) = 1
if you want an example of how something apparently solvable by recursion can grow very ugly very quickly.
Brian Hooper
2010-07-06 16:20:59
If and only if? You have obviously never programmed in a functional language.
Daniel Pryden
2010-07-06 16:21:49
"No other method could possibly be correct?" That is an absolutely silly thing to say. I can't think of a problem that can be solved using recursion that can't be solved with an iterative approach as well.
Adam Crossland
2010-07-06 16:33:27
That seems a bit extreme. Is there ANY problem that could ONLY be solved using recursion? I suspect that if you worked hard enough and were creative enough you could always find another solution, not necessarily efficient or maintainable.
Jay
2010-07-06 16:36:34
We're all scoffing now, but some day in the future, we'll all brag that we were there at the genesis of the seminal computer science paper, "Recursion Considered Harmful."
Adam Crossland
2010-07-06 16:50:39
Adam, you are quite right. Perhaps I was put off recursion from having to fix problems created by bright young programmers using recursion because they liked the idea, rather than because it was what the problem demanded.
Brian Hooper
2010-07-06 17:02:20
+5
A:
Generally, if you can conceptualize the problem with a tree data structure then you can use recursion to navigate the tree.
P.Brian.Mackey
2010-07-06 16:21:57
Though the recursion would explode very soon if its actually a tree structure instead of linear.
apoorv020
2010-07-06 16:29:35
Methinks you links to the wrong tree thar. Try this: http://en.wikipedia.org/wiki/Tree_%28data_structure%29
WCWedin
2010-07-06 16:33:07
@apoorv020: Not necessarily. Remember, the maximum depth of a balanced binary tree is only log N of the number of nodes, and recursive algorithm shouldn't need more stack space than that.
Daniel Pryden
2010-07-06 16:35:56
@apoorv020: In practice, a lot of trees diverge in clusters, with large spurts of breadth at the end or long linear runs in between. Think about, say, a navigation tree for a complex website. Or, if you're dealing with something a little more functional, where a fairly small number of inputs are likely to be repeated, memoization can save you on that point.
WCWedin
2010-07-06 16:38:50
A:
I would NOT use it if you know your language / environment has a limitation on the calling stack depth. I remember working with an early version of Lotus Notes which had a limit of something like 16 levels deep - which would make almost any use of recursion impossible.
Ed Schembor
2010-07-06 16:32:23
Lotus Notes would be an edge case, I think. I'd hardly consider it an argument against using recursion. EVERY environment has some limitation of stack depth.
Adam Crossland
2010-07-06 16:37:40