-1

Recursion - when would you use it and when wouldn't you use it?

Cœur
  • 37,241
  • 25
  • 195
  • 267
ash 2010
  • 329
  • 2
  • 9
  • 14
    To understand when to use recursion, you must understand when to use recursion. :) – btreat Jul 06 '10 at 16:17
  • 1
    Is there a specific situation you have in mind that you are wondering abotu or is it just a vague general question? – Chris Jul 06 '10 at 16:17
  • In soviet russia, recursion uses YOU! – Jukebox Jul 06 '10 at 16:21
  • If you have OCD - look for it to use it to look for it to use it to look for it... etc – Barrie Reader Jul 06 '10 at 16:24
  • 1
    which is the point of view? some algorithms may be expressed in term of recursion more naturally and easily; but it means no they will be performant. – ShinTakezou Jul 06 '10 at 16:28
  • 3
    ...must we have the recursive advice *every* time anyone mentions recursion? – dmckee --- ex-moderator kitten Jul 06 '10 at 16:35
  • 1
    http://stackoverflow.com/questions/3021/what-is-recursion-and-when-should-i-use-it – dmckee --- ex-moderator kitten Jul 06 '10 at 16:37
  • 1
    How does a question of this sort "lead to confrontation and argument"? Someone wants to know when a particular programming technique is useful. If that leads to argument there must be a lot of very touchy people on this forum. – Jay Jul 06 '10 at 16:44
  • @Jay: I'm not saying that you're wrong, but take a look at the discussion that's taken place below. – Adam Crossland Jul 06 '10 at 16:48
  • It is an interesting discussion, useful. So is this Q closed because of that interesting discussion? (Could have been enough to add the "subjective" tag?) - more realistic closing reason would have been "it's a duplicate". – ShinTakezou Jul 06 '10 at 17:07
  • @Shin: The question should be closed as a duplicate. That a majority of the closer got the wrong reason is immaterial in the end. – dmckee --- ex-moderator kitten Jul 06 '10 at 18:19
  • @dmckee ok, but I disagree: if it would be "immaterial", there should be no different "reasons" for closing, but one: 5 persons have voted to close it. – ShinTakezou Jul 06 '10 at 20:24
  • @crossland: I don't want to argue about whether or not people are arguing, but I don't see an argument here. Posters have offerred some suggestions and some have pointed out flaws in those suggestions. How is this any different from thousands of other questions on this site? Are you saying that if anyone says, "The previous poster is incorrect", that the discussion should immediately be stopped for fear that physical violence will ensue? – Jay Jul 07 '10 at 13:38

6 Answers6

9

I use recursion whenever I encounter a problem that requires recursion.

Community
  • 1
  • 1
Daniel Pryden
  • 59,486
  • 16
  • 97
  • 135
  • Why does this have a downvote? – Cam Jul 06 '10 at 16:18
  • Someone with no sense of humour. +1 from me. – Brian Hooper Jul 06 '10 at 16:23
  • 6
    @incrediman I downvoted it because I thought it was a tired joke, unhelpful at best (and at worst, offensive to the OP). – ChrisW Jul 06 '10 at 16:23
  • 1
    @Jesse: I did. The base case is when I don't have a problem that requires recursion. – Daniel Pryden Jul 06 '10 at 16:24
  • 2
    @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 Jul 06 '10 at 16:27
  • 2
    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 Jul 06 '10 at 16:29
  • 2
    I didn't take this is a flippant answer at all. It is an appropriately general answer to an impossibly general question. – Adam Crossland Jul 06 '10 at 16:30
  • @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 Jul 06 '10 at 16:31
  • 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 Jul 06 '10 at 16:32
  • 1
    @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 Jul 06 '10 at 16:34
  • 1
    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 Jul 06 '10 at 16:36
  • 5
    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 --- ex-moderator kitten Jul 06 '10 at 16:36
  • @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 Jul 06 '10 at 16:41
  • 1
    @Justin: how can proper tail calls cause problems? – Adam Crossland Jul 06 '10 at 16:43
  • @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 Jul 06 '10 at 16:49
  • 2
    @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 Jul 06 '10 at 16:52
  • @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 Jul 06 '10 at 16:56
  • @Adam - Does C# require the use of Trampolining to actually keep from growing the call stack (sounds like an interesting IL exercise)? – Justin Niessner Jul 06 '10 at 16:59
  • @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 Jul 06 '10 at 17:01
  • @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 Jul 06 '10 at 18:16
  • @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 Jul 06 '10 at 18:18
  • @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 Jul 06 '10 at 20:32
  • @ShinTakezou: You might want to check out this question: http://stackoverflow.com/questions/491376/why-doesnt-net-c-eliminate-tail-recursion – Daniel Pryden Jul 06 '10 at 21:22
  • I didn't vote, but this is an old joke even in SO. It used to be funny. – Amarghosh Jul 07 '10 at 06:52
5

Generally, if you can conceptualize the problem with a tree data structure then you can use recursion to navigate the tree.

P.Brian.Mackey
  • 43,228
  • 68
  • 238
  • 348
  • Though the recursion would explode very soon if its actually a tree structure instead of linear. – apoorv020 Jul 06 '10 at 16:29
  • 3
    Methinks you links to the wrong tree thar. Try this: http://en.wikipedia.org/wiki/Tree_%28data_structure%29 – Isabelle Wedin Jul 06 '10 at 16:33
  • @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 Jul 06 '10 at 16:35
  • @apoorv020: Not necessarily. It depends how tall the tree is. – Jay Jul 06 '10 at 16:37
  • @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. – Isabelle Wedin Jul 06 '10 at 16:38
  • @WCWedin. Lol, yea that tree. – P.Brian.Mackey Jul 06 '10 at 17:54
2

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
  • 242,243
  • 40
  • 408
  • 536
  • See also [When do you worry about stack size?](http://stackoverflow.com/questions/1915900) – ChrisW Jul 06 '10 at 16:20
  • 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 Jul 06 '10 at 16:20
  • 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 Jul 06 '10 at 16:40
2

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
  • 1,726
  • 16
  • 32
0

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
  • 8,090
  • 8
  • 31
  • 37
  • 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 Jul 06 '10 at 16:37
-1

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
  • 21,544
  • 24
  • 88
  • 139
  • 3
    If and only if? You have obviously never programmed in a functional language. – Daniel Pryden Jul 06 '10 at 16:21
  • 1
    Maybe he meant he would never use recursion... – Wayne Werner Jul 06 '10 at 16:22
  • 1
    "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 Jul 06 '10 at 16:33
  • 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 Jul 06 '10 at 16:36
  • 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 Jul 06 '10 at 16:50
  • 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 Jul 06 '10 at 17:02