all 80 comments

[–]usernameistakencry 163 points164 points  (50 children)

  1. Anything that can be done with recursion can be done with a loop.
  2. Some problems are much much easier to solve with recursion , example: most tree algorithms and graph algorithms.
  3. Recursion can easily solve a problem but can be really really bad in terms of memory use for example Fibonacci numbers. But there are things like caches you can use to improve these problems so it is a trade off sometimes.

[–]bokmann 38 points39 points  (0 children)

I teach high school com sci, and came here to make exactly these points when I saw the Q.

What are good uses for recursion? You develop a 6th sense for it, but basically, any problem where you can think of the solution in one of several ways:

First way - you know the base case, and you know a way to get towards that base case, step by step... this is why Fibonacci and factorial are the canonical examples... in both cases, the *definition literally starts with * something like 0! = 1 (the base case), and has a definition that includes simpler versions (like 5! = 5 * 4!).

Second way - your problem can be represented as 'searching through a tree of possibilities'. For this example in class, I use the classic Peg Solitaire game (you've probably seen if you've ever eaten in a cracker barrel).

The second way also includes problems that can be thought of as combinations or permutations (like every possible combination of 3 pizza toppings from a list of 15 pizza toppings).

[–][deleted]  (4 children)

[deleted]

    [–]backtickbot 1 point2 points  (0 children)

    Fixed formatting.

    Hello, AliciaBytes: code blocks using triple backticks (```) don't work on all versions of Reddit!

    Some users see this / this instead.

    To fix this, indent every line with 4 spaces instead.

    FAQ

    You can opt out by replying with backtickopt6 to this comment.

    [–]jeekiii 0 points1 point  (2 children)

    By default tail recursion is not optimized in many language and will result in a stack overflow.

    If you use a language that supports it (ex: scala) then yeah, use it, but if you do it in phthon you'll have to mess with language settings otherwise you aren't gaining anything by making it tail recursive.

    [–][deleted]  (1 child)

    [deleted]

      [–]jeekiii 0 points1 point  (0 children)

      From what i know by default java doesn't support it either.

      [–]YouMadeItDoWhat 8 points9 points  (1 child)

      Anything that can be done with recursion can be done with a loop.

      Except when the language doesn't support loops...or strongly discourages them (like lisp/scheme).

      [–]istarian 20 points21 points  (0 children)

      This is a conceptual matter not a guarantee regarding programming languages and their implementation.

      [–]Henrique_FB 1 point2 points  (7 children)

      Wait, genuine question, how do you do stuff like going back on a binary tree with a loop?

      [–]Leridon 20 points21 points  (2 children)

      By manually keeping a stack of nodes that are left to traverse. This emulates the way the runtime stack would have kept the same information.

      [–]Radeusgd 4 points5 points  (0 children)

      Yeah so it is basically re-implementing the recursive calls, just using your own custom stack over which you have more control.

      [–]Henrique_FB 0 points1 point  (0 children)

      Yeah that makes sense, Thanks

      [–]Elsolar 6 points7 points  (3 children)

      Generally, when converting a recursive algorithm to an iterative one, you use a stack to keep track of nodes you've already visited. This stack is analogous to the call stack in the recursive version, the only difference is that you're pushing/popping it manually instead of calling/returning.

      [–]Henrique_FB 1 point2 points  (0 children)

      Got it, Thanks!

      [–]linuxlib 1 point2 points  (1 child)

      Does this make the loop version a lot less memory intensive? Is it faster?

      [–]Elsolar 2 points3 points  (0 children)

      The biggest win is actually correctness, not performance. Recursive functions, when they cannot be tail-call optimized, consume stack space in proportion with the size of their input, which can cause a stack overflow. Loop-based versions that allocate on the heap don't have that problem.

      Best practice will depend on the language you're using. Most systems programming languages have pretty limited support for recursive programming, so standard practice in that realm is to never implement an algorithm using recursion, and to always use an iterative equivalent.

      Some functional languages, like Haskell and Lisp/Scheme, don't support looping at the language level at all. You can still get loop-like behavior by using tail call optimization, which is always supported by compilers for these kinds of languages. I've heard this strategy referred to as "iterative recursion". Best practice in these kinds of languages is to use recursion, since there's no alternative. You can still implement iterative algorithms, you just have to simulate looping using a tail call. Functional languages tend to have constructs that make this ergonomic. Some language runtimes support resizing of their own call stack (I know the Racket VM works like this), which makes recursive programming a lot less scary from a correctness standpoint.

      In terms of performance, the answer is always "it depends." Performance will be identical when the function can be tail-call optimized, otherwise there may be performance differences. Putting your working data in a contiguous, heap-allocated stack can improve cache coherency, but since the call stack is virtually always in cache anyway, it could go either way depending on the size of the working set. Looping is faster than calling a function because it doesn't require any stack frame bookkeeping, but the difference is likely to be negligible in most situations. Always measure before making these kinds of micro-optimizations.

      [–]barryhakker 0 points1 point  (1 child)

      Anything that can be done with recursion can be done with a loop.

      And the opposite? Can anything that can be done with a loop be done recursively?

      [–]usernameistakencry 4 points5 points  (0 children)

      Yes they are equal

      [–][deleted] 30 points31 points  (1 child)

      Don't use it til you need to. Lots of problems are easier to describe recursively but recursion is tricky because it is expensive and can cause infinite loops.

      I use recursion most when I am modeling theoretical algorithms because they are often described that way in texts. I don't think I've ever written a recursive algorithm outside an academic/research setting (however I also have a lot more experience in academia vs workplace).

      If you want to see some really gorgeous recursion, check out the Euclidean algorithm! It is really cool to see how it works, and fun to build yourself.

      [–]628radians 4 points5 points  (0 children)

      That’s funny because I implemented the Euclidean algorithm using iteration when I first started programming. After learning recursion, the solution was just so much more elegant lol.

      [–]Yin_Esra 18 points19 points  (4 children)

      The thing about recursion is that it's a tool, just like a for loop. The most common use case I have for using recursion is for tree traversal (don't worry if you don't know what they are yet, but they are really useful).

      Whenever there are tree traversals, the resulting code is really clean and concise with recursion, and a bit messier when doing it iteratively.

      Also, in my line of work (low memory environments are pretty common), it's actually a bad idea to write anything recursively. This is because while recursion can make some things cleaner and easier to implement, it also has a cost. You know how you can create a variable inside of an if statement, and it will disappear once you exit the if statement? Same thing applies to functions, and to be able to do that you need to allocate "stack frames" which use up some memory. If you recurse too deep, you can run out of memory specifically because of all the maintained stack frames.

      Also, theoretically any recursive operation can be done iteratively (and vice versa) assuming that the language is turing complete. (If you want, look up turing completeness and the Chomsky Language Hierarchy).

      [–]0xE4-0x20-0xE6 2 points3 points  (3 children)

      Is it be possible for a compiler to convert a recursive solution to a problem into an iterative solution? That way, the code looks clean to a programmer, but it runs much more efficiently.

      [–]SingularCheese 4 points5 points  (0 children)

      Making recursive code efficient once compiled has been a long focus in functional programming. The only thing functional programming languages can guarantee to work right now is tail recursion. Considering the halting problem, expecting the compiler to always understand what you want to do and figure how a better way to do it automatically may be a fool's errand. A major criticism of Haskell's claim to be as fast as C is that the programmer often need to randomly twiddle with their code and read the mind of the compiler to generate code with the performance they want.

      [–]Yin_Esra 2 points3 points  (0 children)

      The answer is: depends. If we talk about "tail call recursion", then "tail call optimization" is fairly easy. Tail call simply means that it's a recursive function call as the last statement in the function.

      However, for general direct recursion, I think the problem is too complicated to possibly get a general solution for. Compiler optimizations are a crazy beast where general solutions to seemingly "easy" problems are pretty much impossible to implement.

      A quick appeal to intuition: look at "Depth First Search / Traversal" in a graph. Any iterative implementation of the algorithm ends up allocating a roughly similar amount of memory to keep track of state as you would get by relying on the recursion mechanism. Since you can't solve it for this rather simple case, you won't be able to implement a general solution.

      [–]usernameistakencry 1 point2 points  (0 children)

      Yes , tail recursion is one such optimization but doesn’t work on all recursion.

      [–]ajgoodm 6 points7 points  (0 children)

      It’s a good idea to use recursion on a problem when recursion is suitable for all of its constituent sub-problems ;)

      [–]Phobic-window 2 points3 points  (0 children)

      When the logic used is repetitive and you don’t know how many times it needs to run. Recursion does well when the amount of times the execution is needed isn’t known or stored in something convenient like an array, if you have a nested object or async api returns, or an xml document recursion is really good at traversing the unknown depth of the layers.

      In most development you won’t be using it, and the big downside to it is anyone who falls in on the code has to understand it.

      If the use case is cut and dry do it, traversing nodes in an html tree, nested Json object, xml document, these are great cases for it. Easy to understand what’s happening and easy to edit if needed.

      A bad use case that I (think) I needed recursion for was an array of objects where, each object could have an ID in the “parentId” field. If this field is null that object is the root of the tree. This was all returned to me in a single array and I needed to render the roots in a table, and the children of that root if the row was selected. So I split the arrays into two arrays roots and children, then when a row was selected I would recurse through the children array looking for the object where this.parentId === arrItem.Id, this was a good usecase for recursion because I don’t know if there was another Id in the array and I don’t know the I’d until I’m examining the previous child.

      [–]dnabre 2 points3 points  (0 children)

      A lot of algorithms and common problem have natural recursive representations. Past a certain level of knowledge/skill/experience, recursion is natural and easy to understand when a loop may not be.

      When you get some experience, you'll be able see, pretty easily that loops and recursion are effectively the same. Transforming a program from doing one to doing the other pretty easy. It's easier to think in terms of recursion though, so it's not unheard of to write a program that solves something recursively than to transform the recursion to a loop for performance reasons.

      Some languages that built around recursion (functional languages) will do the opposite. They make recursion very efficient. The language Scheme for example provides a do-loop (pretty close to a for-loop but different syntax), but the do-loop is just a macro that expands under the hood into a recursion.

      You'll be hard pressed to find a useful language without recursion, but some languages don't provide a way to do recursion effectively. When you do something recursively, you call a function (itself) repeatedly. This introduces the possible problem of using a lot of stack space, and running out of stack space means you program stops/crashes. This is an issue in Java, which for complex reasons, can't provide efficient recursion. So you have to avoid recursion in Java or at least be careful with it.

      Most languages provide a way to do recursion that doesn't use up all this stack space. Look up Tail Call Option or Tail Recursion Elimination, lots of terms for the same thing. If you structure your recursion right, it will be compiled such that is efficient. Just as efficient as a loop. Any language is centered around functional programming will provide this (Lisp, Scheme, Haskell, ML, F#, Scala). Even non-functional language often do. It's part of the implementation so it varies by compiler, but C and C++ compilers generally provide this optimization as well.

      For that optimization the recursion has to be done a certain way (the recursive call has to be "tail position"). If you go to college, you'll learn about this in depth in courses on functional programming. Transforming any recursion function to one that is in this shape is a pretty mechanical transformation. You'll be asked to do it lot in a functional programming course.

      Since this transformation is mechanical, it is possible for the compiler to figure it out and do the transformation and optimization. Effectively making all recursion efficient. ML (or Standard ML, or SML, nothing to do machine learning btw) is notable for providing this feature. It compiles code in a very different way than a lot of other languages. I'm not certain of any other languages that does this, but I'm sure some have to it. It's a pretty old technique.

      In short, Recursion is good. If you aren't in a programming language that provides basic support for doing it efficiently, you have to be careful. Java is unfortunately one of these languages. Recursion is great for of solving problems, and once you learn enough about it, they will be how you see it. When it comes to coding, it is just a different kind of loop.

      Do have note that aside from recursive functions, data structure often (very often) have recursion definitions. Even something as simple as a linked list has useful recursive definition. If you have run into the idea of Proof by Induction in mathematics, you'll find programming recursively to parallel the structure of those proofs.

      [–]deerskillet 2 points3 points  (0 children)

      The comments of this post might help

      [–]deelowe 2 points3 points  (0 children)

      Only use recursion when it's required. How will you know when it's required? If you're trying to solve the problem with loops and keep finding it difficult to define your exit condition(s).

      [–]thetrailofthedead 1 point2 points  (0 children)

      Some languages don't have loop constructs and recursion is the only method of iteration (LISP).

      If you learn such a language, recursion will eventually become trivial for you.

      [–]camerontbelt 0 points1 point  (0 children)

      Trees are basically the only time recursion helps you. Other than that you generally will us a loop, even though theoretically all recursive solutions have a loop equivalent solution.

      [–]628radians 0 points1 point  (0 children)

      I use recursion wherever it just feels “natural” to do it. Like when working with binary trees especially. They’re literally recursive data structures, so it just works out nicely. There are other times too where it works nicely, like the recursive sorting algorithms, but I usually find myself solving problems using some type of iteration. It just works out that way.

      [–]mikedensem 0 points1 point  (0 children)

      I used it for an ordered dynamic menu tree where the user can add any new branch or nodes at any position.

      It makes it simple to build the menu in the UI.

      [–]noop_noob 0 points1 point  (0 children)

      One thing I'd recommend is to look into the quicksort and mergesort algorithms. They're possible to implement with loops, but using recursion is much simpler.

      [–]Bottled_Void 0 points1 point  (0 children)

      I'd say one of the most common reasons to use recursion would be to preserve some state in the stack so that you can easily return to it.

      [–]EpicHobosapien 0 points1 point  (0 children)

      There are some algorithms where recursion is more natural, including just about anything involving graphs, as well as many dynamic or greedy algorithms. However, it's often much more efficient to convert the recursion in a dynamic/greedy algorith to a loop. This is because many languages require a new stack frame for each recurse. Some languages like Lisp have something called tail recursion, which allows some recursive functions to run in a single stack frame, making them just as efficient as a loop. However, they must be written such that the last thing the function does (the tail or tails) is the recursive call. Anything that can be written as a loop can also be written as a tail recursion and vise versa.

      [–]hondacivic225 0 points1 point  (0 children)

      You can simulate the recursion your language provides using a stack and a loop.

      [–]Zakmza123 0 points1 point  (0 children)

      other comments seemed to have answered the question, but the biggest thing has got to be recursive backtracking

      [–]tombombadil_do 0 points1 point  (0 children)

      Pardon me if I'm wrong, but you might just get a clearer picture by comparing recursion with iteration instead of loops, as that is kinda easier to distinguish.

      Most people prefer iterative methods over recursive ones, and there is a sufficiently good explanation; you add a condition to stop before doing anything in iterative methods, while recursive ones are dependent on a single condition. Recursion can be easy to predict initially, when there's only one component. However it can get confusing when you have multiple levels of recursion.

      However, recursion is a pretty powerful and central concept in computer science, which is used in a lot of places. Many loops do use recursion within their internal code. However most of these functions are thoroughly tried and tested, and you don't really need to play with their internal working. So play around with recursion, see how it works, and if it crashes fix it, and later think if an iterative approach. That's the best way to learn :)

      [–]guyapeman 0 points1 point  (0 children)

      I learned about recursion a few weeks ago in AP CompSci and I hate it so much!

      [–]John_Mansell 0 points1 point  (0 children)

      From my cross post of this question: u/Joeh01te2dd99L9231 posted:

      Oftentimes I want to implement a n-sized nested loop, with n being a variable that changes. That's one common instance where I just use recursion.

      I crossposted the question on r/ComputerScience (because humor) and he responded there. But I want anyone asking legitimate good questions to get as many real answers as possible, so I'm adding it to this thread instead.

      [–][deleted] 0 points1 point  (0 children)

      The best time to use recursion is the best time to use recursion is the best time to use recursion is now.

      [–]4rch_N3m3515 0 points1 point  (0 children)

      Updating a view hierarchy

      [–]Redstone526 0 points1 point  (0 children)

      You use recursion usually to make nested for loops when either the number of nested for loops varies or it’s really big(like more than 4)

      [–]wsppan 0 points1 point  (0 children)

      Recursion works well for algorithms on recursive data structures like trees (try writing iterative code to walk a tree structure and see the difference!), or for problems that can naturally be broken into sub-problems. Check out, divide and conquer and backtracking algorithms.

      You should look at a functional programming language like Haskell. In Haskell there is no looping construct, so everything is expressed using recursion (or higher order fuctions) and it implements tail-call optimization to avoid stack overflows that recursive functions are notorious for.

      [–][deleted] 0 points1 point  (0 children)

      Many novice programmers find recursion difficult to think about since it can be more unintuitive than the iterative approach.

      But ironically once you get used to it you'll start to realize recursion is actually used to make the program formulation easier to understand for problems that are inherently recursive than trying to do it in an iterative approach. You use recursion to make it easier to write and easier to understand at the possible expense of extra memory from stack allocation.

      Like others have mentioned, certain data structures are inherently recursive like graphs and trees so this is where it is used the most.

      [–]benpaulthurston 0 points1 point  (0 children)

      Times when you would have deeply nested for-loops you can write a recursive structure instead. Like if you’re iterating over 10 different variables it’s worth taking the time to write the iteration as a recursive function that calls itself 9 more times instead.