r/computerscience • u/UselessPlinth • 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?
31
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
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
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
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
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
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.
163
u/usernameistakencry May 03 '21
Anything that can be done with recursion can be done with a loop.
Some problems are much much easier to solve with recursion , example: most tree algorithms and graph algorithms.
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.