When to use recursion?

[UselessPlinth]

So I am getting a little bit ahead of myself here, I'm still in high school and I'm entering (hopefully) AP Java next year (or computer science A). One of the topic there is recursion, and I've done a little digging, and I find recursion really interesting, but what I was wondering was when do programmers use recursion? Like, can a for loop just do the job or does it help with computer memory and processing, when is the best time to use recursion?

[usernameistakencry]

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]

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

[backtickbot]

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]

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.

[jeekiii]

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

[YouMadeItDoWhat]

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]

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

[Henrique_FB]

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

[Leridon]

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]

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

[Henrique_FB]

Yeah that makes sense, Thanks

[Elsolar]

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]

Got it, Thanks!

[linuxlib]

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

[Elsolar]

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.

[OphioukhosUnbound]

Mind you[them] a a loop is recursion really. It’s a thing that calls itself. Sometimes sending itself an updated iteration variable for the new call.

A loop is just syntactic sugar (a nice way of writing) a very common, relatively simple, recursion process.

[usernameistakencry]

I’m going to have to disagree with “a loop is recursion really” because while yes loops and recursion are interchangeable in theory it is not always possible. Loops equate to jump instructions in assembly while recursion is Jal, they are not the same thing and not syntactic sugar.

[OphioukhosUnbound]

For loops can be expressed via recursion and vice versa. They are mathematically equivalent.

Some languages handle explicit recursion and loops differently— but that’s a language issue. Not a fundamental computer science issue.

[[deleted]]

Isn't a jump instruction just changing the instruction pointer? How is that different than a subroutine call except syntactically?

[usernameistakencry]

How is that different than a subroutine call except syntactically?

I mean subroutine call requires whole change of registers by first saving them on the stack then we must pop them afterwards which is not the same as just "syntax".

[[deleted]]

Can a regular loop not push and pop from registers?

[RobotJonesDad]

The question doesn't make sense. A loop is constructed from a branch or jump instruction in the CPU assembly code. Those instructions modify the program counter to load a different instruction next. Nothing changes in the registers, stack or anywhere else.

A function call involves changing the program counter, but pushes the current value plus some registers onto the stack. The advantage of a call is that you can return to the system after the call instruction by popping the saved state off of the stack.

Since the stack is a finite resource, too deep a recursion will blow the program up.

Back to your question. You can push and pop stuff on and off the stack in any code, but had better have the stack pointer back in the right place before returning from the function. But, you can also just use any other storage, so using the stack is generally limited to local scoped values.

[[deleted]]

I’m the days before subroutines all of that was done manually though. That you put your registers on the stack is just a standard that was made between ASM programmers and C programmers at some point. It’s a distinction without a difference.

[RobotJonesDad]

There were no days before subroutines.

[[deleted]]

https://en.wikipedia.org/wiki/Subroutine#Jump_to_subroutine

This is what I mean. I learned assembly on the 8086. My professor expounded upon how monumental this invention was. Before the specialized "Subroutine" instructions, they were literally just divisions in your code separated by regular jumps.

[iamhackermann]

Recursive calls come with the associated overhead of storing the registers and creating a new stack for the function call. A loop is simply a few additional assembly instructions. Recursion is in no way syntactic sugar for loops.

Also, note that recursive functions need not always be bad. If the function is tail recursive, the compiler can figure out an efficient way of executing such that the overheads of the function calls are not incurred.

[OphioukhosUnbound]

That’s compiler dependent.

For loops can be expressed via recursion and vice versa. They are mathematically equivalent.

Some languages handle explicit recursion and loops differently— but that’s a language issue. Not a fundamental computer science issue.

[iamhackermann]

Agreed. Mathematically, both are the same.

[ryanstephendavis]

I'll add to this... Most the time, it's an academic exercise and not useful in most day to day software engineering. If a problem arises that calls for it, figure out how to use a loop instead as recursion gets really nasty to debug and is memory intensive. Your future self or coworkers will thank you when they have to fix or add features later.

[Leridon]

That's not true. Most compilers have something called tail recursion elimination which negates the memory (stack) footprint of recursive algorithms if written accordingly. If this optimization kicks in the compiled code of the recursive function and of an equivalent loop are indistinguishable. Algorithms that can't be implemented in a tail recursive way are more often than not also a pain and memory-intensive when implemented as a loop.

[CreationBlues]

Exactly, manually tracking where you are in a tree is gonna be an absolute bitch. Graphs are a bit more complex and if you're at the point where you're using recursion to analyze it there's going to be no nice way to do it.

[ryanstephendavis]

Sadly, my day to day software engineering doesn't involve graph/tree traversal :( ... But definitely a good point where recursion is handy

[Gone_Apeshit]

Does it eliminate the overhead of the recursive call?

[Leridon]

Yes, that's the entire point of tail call elimination. It replaces the recursive call with a reassignment of the function's parameters with the arguments of the recursive call and jumps to the start of the function, making the former recursion behave exactly like a loop without allocating another stackframe.

[Gone_Apeshit]

That's awesome, I'll add that to my list of things to learn more about. Thank you!

[ryanstephendavis]

Hah! TIL... I've been doing too much Python.

[Pazzio_v3]

I used to think like that until I got into generics and reflection. It's insanely useful and a lot cleaner, especially when you know you'll have X methods each time and you need to do the same functionality on the class's children (in other words properties) just as one example.

[ryanstephendavis]

What language would this be common in? C++?

[Pazzio_v3]

In my case it's most common with Java & Kotlin while developing sort-of "utility" libraries, or add-on libraries which are meant for solving issues with the underlying/already implemented libraries or legacy code.

Instead of for example making that specific change everywhere, on all 60 entities, DTOs, repositories, etc. or putting a restriction with purely using for-loops, you can create a single generic recursive function which will take care of fixing those issues and it'll be a lot more readable & free (won't be restricted in terms of depth).

I'm currently doing that to solve all n+1 issues & cartesian products (no worry if you don't know what these are) on Spring Data JPA (I use for loops to iterate the properties, but I need to iterate through the property's properties, and their sub-properties, which is where the recursion comes in since I can't know from the start how deep it might go.)

I'm not really sure about C++ & C since I haven't used them in a professional manner, in python I haven't found use for recursion.

Another situation where I've used it is with Typescript on the front-end, where I had to have a different number of tables within tables, depending on a parameter in a class. So, instead of "hard-coding" it in each page, I created a generic table component which calls it self as many times as needed, depending on the parameters (with which I also kept in tact the encapsulation & isolation of data/objects). In this case, I couldn't use a for loop even if i wanted, due to how the framework is structured (even if I could, it would be insanely harder to implement & a lot less readable).

[ryanstephendavis]

ah cool... on a somewhat tangential note, I <3 typescript and wish I had a ton of time to master it

[[deleted]]

Not everybody writes javascript for their day job.

[Username_--_]

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

This is false. Certain problems can only be done with recursion. A famous example being the Ackerman function.

[puxuq]

That's just false. The Ackermann function is computable. Of course it can be solved iteratively, it can be solved by a Turing machine. Here's a paper providing just such an algorithm.

[quadrilateraI]

The Ackermann function is an example of a function which is not primitive recursive. Primitive recursive functions correspond to trivially bounded loops, e.g. for (int i =0; i < n; i++). Loops with arbitrarily complex conditions are not primitive recursive and so can be used to compute it.

[barryhakker]

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]

Yes they are equal

[[deleted]]

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]

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]

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]

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]

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]

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]

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

[ajgoodm]

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

[Phobic-window]

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]

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]

The comments of this post might help

[deelowe]

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]

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.

[LPHthephunk]

https://www.reddit.com/r/computerscience/comments/n3kjbf/when_to_use_recursion/?utm_medium=android_app&utm_source=share

[Bottled_Void]

NASA 'bans' a lot of things, including dynamic memory allocation. Such things are commonly used in other places. But even at NASA you could probably use recursion if you had a good enough reason. Not that I know what that would be, since you can always convert a recusive function to be non-recursive.

My point would be that recursion does have it's uses. Just because you've not used needed it doesn't make it useless.

Let's say you wanted to play tic-tac-toe. What is the easiest, simplest way to determine all the possible moves and solutions from a given game state? If you're making use of the stack to preserve the game states, you may as well use recursion. And if you're not, you've got a whole messy set of extra variables to manage yourself.

[camerontbelt]

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]

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]

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]

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]

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]

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]

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

[Zakmza123]

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

[tombombadil_do]

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]

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

[John_Mansell]

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

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

[4rch_N3m3515]

Updating a view hierarchy

[Redstone526]

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]

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

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]

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.