r/computerscience • • May 03 '21

When to use recursion?

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?

141 Upvotes

80 comments sorted by

163

u/usernameistakencry May 03 '21
  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.

39

u/bokmann May 03 '21

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

9

u/YouMadeItDoWhat May 03 '21

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

21

u/istarian May 03 '21

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

3

u/Henrique_FB May 03 '21

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

20

u/Leridon May 03 '21

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.

6

u/Radeusgd May 03 '21

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

1

u/Henrique_FB May 03 '21

Yeah that makes sense, Thanks

6

u/Elsolar May 03 '21

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.

2

u/Henrique_FB May 03 '21

Got it, Thanks!

2

u/linuxlib May 03 '21

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

3

u/Elsolar May 03 '21

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.

1

u/barryhakker May 03 '21

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?

5

u/usernameistakencry May 03 '21

Yes they are equal

-9

u/OphioukhosUnbound May 03 '21

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.

11

u/usernameistakencry May 03 '21

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.

10

u/OphioukhosUnbound May 03 '21

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.

2

u/[deleted] May 03 '21

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

2

u/usernameistakencry May 03 '21

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

1

u/[deleted] May 03 '21

Can a regular loop not push and pop from registers?

1

u/RobotJonesDad May 04 '21

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.

1

u/[deleted] May 04 '21

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.

1

u/RobotJonesDad May 04 '21

There were no days before subroutines.

1

u/[deleted] May 04 '21

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.

→ More replies (0)

3

u/iamhackermann May 03 '21

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.

6

u/OphioukhosUnbound May 03 '21

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.

3

u/iamhackermann May 03 '21

Agreed. Mathematically, both are the same.

-5

u/ryanstephendavis May 03 '21

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.

11

u/Leridon May 03 '21

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.

2

u/CreationBlues May 03 '21

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.

1

u/ryanstephendavis May 04 '21

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

1

u/Gone_Apeshit May 03 '21

Does it eliminate the overhead of the recursive call?

6

u/Leridon May 03 '21

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.

3

u/Gone_Apeshit May 03 '21

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

1

u/ryanstephendavis May 04 '21

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

4

u/Pazzio_v3 May 03 '21

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.

2

u/ryanstephendavis May 04 '21

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

1

u/Pazzio_v3 May 06 '21 edited May 07 '21

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

2

u/ryanstephendavis May 11 '21

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

1

u/[deleted] May 03 '21

Not everybody writes javascript for their day job.

-6

u/Username_--_ May 03 '21

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.

9

u/puxuq May 03 '21

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.

1

u/quadrilateraI May 04 '21

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.

0

u/[deleted] May 03 '21

[deleted]

2

u/backtickbot May 03 '21

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.

1

u/jeekiii May 04 '21

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.

0

u/[deleted] May 04 '21

[deleted]

1

u/jeekiii May 04 '21

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

31

u/[deleted] May 03 '21

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.

6

u/628radians May 03 '21

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.

19

u/Yin_Esra May 03 '21

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

3

u/0xE4-0x20-0xE6 May 03 '21

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.

5

u/SingularCheese May 03 '21

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.

3

u/Yin_Esra May 03 '21

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.

2

u/usernameistakencry May 03 '21

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

6

u/ajgoodm May 03 '21 edited May 04 '21

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

4

u/Phobic-window May 03 '21

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.

3

u/dnabre May 03 '21

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.

3

u/deerskillet May 03 '21

The comments of this post might help

3

u/deelowe May 04 '21

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

2

u/thetrailofthedead May 03 '21

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.

1

u/camerontbelt May 03 '21

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.

1

u/628radians May 03 '21

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.

1

u/mikedensem May 03 '21

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.

1

u/noop_noob May 03 '21

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.

1

u/Bottled_Void May 03 '21

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.

1

u/EpicHobosapien May 03 '21

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.

1

u/hondacivic225 May 03 '21

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

1

u/Zakmza123 May 03 '21

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

1

u/tombombadil_do May 03 '21

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

1

u/guyapeman May 03 '21

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

1

u/John_Mansell May 03 '21

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.

1

u/[deleted] May 04 '21

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

1

u/4rch_N3m3515 May 04 '21

Updating a view hierarchy

1

u/Redstone526 May 04 '21

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)

1

u/wsppan May 04 '21

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.

1

u/[deleted] May 04 '21

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.

1

u/benpaulthurston May 12 '21

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.

-7

u/[deleted] May 03 '21

[removed] — view removed comment

2

u/Bottled_Void May 03 '21

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.