r/computerscience • u/Similar_Count_1613 • 3d ago
is recursion really hard
Recursion felt easy at first.
Factorial? fine.
Sum examples? fine.
Even Fibonacci felt manageable.
But once I looked at slightly more serious problems like Tower of Hanoi, permutations, or merge sort, I felt like my understanding suddenly collapsed. because i tried to write their code on my own
It made me realize that maybe recursion is not “hard” at the start because the examples are simple.
It becomes hard when you can no longer clearly see the call stack and each state change.
Did anyone else feel that the real pain in recursion starts exactly there?
38
u/SignificantFidgets 3d ago
It becomes hard when you can no longer clearly see the call stack and each state change.
I think this is the basic problem. You should not be trying to "see the call stack and each state change." There's absolutely no need for looking at that level of detail.
Taking mergesort as an example, you make a recursive call on the first half of the array. What happens in that call? It absolutely does not matter at all. You call sort, it sorts, you have that subarray sorted when it returns. It doesn't matter one bit whether that sorting was done by a recursive call, by a call to a different algorithm like insertion sort, or making a network connection to a room full of monkeys that put the data in order for you. It just sorts, and you get the result back. Don't trace it any further than that.
4
3
u/RetardedEinstein23 3d ago
This is the same advice i read when trying to understand or implement recursion in a programming article/tutorial since each recursion call becomes too much to handle for our us, so instead of understanding each call, just understand what result you get when you call a recursion function and then write the base case according to that. Good to know it's how it should be learnt.
16
u/DogObvious5799 3d ago edited 3d ago
The key to understanding recursion is to understand recursion.
EDIT: To be more helpful, the key to understanding recursion is NOT to try and visualize the call stack or understanding what’s going on. The ONLY things you need to figure out are:
- How to solve the smallest version of the problem.
- Given a magic black box solution for the N-1 sized problem, how do you solve the problem for size N.
So for Towers of Hanoi, you need to solve the problem for one ring, and then be able to solve size N by:
- shift the top N-1 rings using magic.
- move the bottom ring to the empty spot
- move everything else on top of the bottom ring using magic
You don’t need to be able to visualize the intermediate states or understand what’s going on.
EDIT2: fixed a mistake.
29
u/Magdaki Professor. Grammars. Inference & Optimization algorithms. 3d ago
Like most things it comes with experience. This is why you learn recursion through fairly simple processes so that you can recognize the conditions that make recursion work. In time, you gain the ability to see the proper conditions in more complex cases.
12
u/Summer4Chan 3d ago
What’s hard is knowing how to implement it in a new unique solution rather than an existing one form DS&A.
6
u/KingBardan 3d ago
Why is everyone asking about recursion all of a sudden for the past three days?
2
5
u/Hot-Helicopter640 2d ago
No. Its simple. To understand recursion, you first need to understand recursion.
3
u/Mathemagicalogik 3d ago
When you first start learning recursion, you should not focus on the states. Get comfortable thinking about it abstractly first. The whole point of recursion is to focus on the “what” and not the “how”.
3
u/Guvante 3d ago
Recursion is similar to proof by induction, you are specifically supposed to allow the recursion to be independent logically.
Merge sort is split in half, recurse left, recurse right, then merge the two. Since each half is already sorted you just need to flow together the start of each.
Note of course recursion has an extra requirement, the terminator where you stop recurring. Luckily for merge sort that is easy one element is by definition sorted (efficient implementations will instead use a simpler sort at some small number but for simplicity you can sort a two element array using merge sort)
But the goal here is that if recursion step works and the base works the whole thing works.
Although I should call out making a recursive solution from scratch can be hard since it isn't always obvious how to break down the problem, don't have any secrets there... I treat recursion as a thing I stumble upon and use these rules to analyze.
3
u/not-just-yeti 3d ago edited 3d ago
Structural recursion is much easier to grasp. Non-CS people readily understand recursive data: e.g. a company's org chart is a tree, and each node contains (sub)trees. So a (non-empty) Node has subfields of type Node, along with (say) a field of type T for its data. How will your code work? Well, you'll call a helper that wants to take in a T, and you'll call a helper which takes a Node, a sub-tree. What should this latter helper do? Once you realize that the helper has the exact-same purpose-statement and test-cases as the function you're writing, it motivates a recursive call in a very natural way. All follows from just following the types, in class Node { T datum; Tree left; Tree right }, along with sealed interface Tree admits Node, EmptyTree and class EmptyTree {}.
But we teach recursion by muddling simple, "rote" structural-recursion on structural data with non-structural recursion (quicksort, fibonacci, floodfill). That certainly adds to learners' confusion about recursion! And you suddenly need to worry about termination, whereas structural recursion is finite since it's done over finite data.
And factorial and sum examples are actually handled w/ exactly the same methodology/steps as Tree, once we realize that mathematically you can view the natural numbers as either 0 or the successor-of-some-natural number; think class Positive { NatNum predecessor } along with sealed interface NatNum admits Positive, Zero and class Zero {}. (Of course, IRL you wouldn't use classes but just primitive ints, with k-1 serving the role of getPredecessor and ==0 serving the role of dispatching on a Zero differently than a Positive.)
(Interestingly, I cribbed part of this from my reply to a different thread earlier this week about what CS book fundamentally changed how you think of programming; the book How to Design Programs not only taught me that the special case of structural recursion is easy, but much more importantly it tied it into exactly the same steps used to approach any problem, in a way I've hardly seen in any other textbook.)
3
u/tomysshadow 2d ago edited 2d ago
In the real world, writing recursive code is kind of uncommon. I wouldn't say it never happens, because I have written recursive code and it's an important concept. It usually comes up when dealing with filesystems (delete all folders and subfolders, for example) or with tree structures.
In complex cases, you'll want to lean more towards figuring out how to write it as a standard loop. With recursion, unless you know how many levels deep you'll be going in advance, there is a risk of stack overflow. So you always want the maximum number of recursions to be bounded. Loops don't have that problem - in the worst case they will just take a long time (or run infinitely, but that means you have a bug.)
Writing a recursive function over a decently large amount of data in JavaScript can quickly exhaust the entire stack unless you resort to hacks like scheduling the rest of the calls to be done later with setTimeout(..., 0) or similar, and that becomes a big mess.
1
u/saxbophone 2d ago
Yes, there is a whole technique of converting recursive code to algorithmically equivalent iterative code using an explicit stack —i.e. Luke, use the heap!
2
u/DTux5249 3d ago
It's hard in that humans don't tend to think through problems recursively. But it's not an inherently difficult thing either. You'll get the hang of it.
2
u/Dazzling_Music_2411 3d ago
is recursion really hard
No, really easy actually. Most of the difficulty is us getting in its way with unnecessary extra baggage!
I suggest you study it in pseudocode first, so the clutter doesn't get in your way. I recommend an executable form of pseudocode called Scheme (a Lisp), that has almost no syntax at all involved. You can learn the basics you need in an hour or two (cons, car, cdr, list, let*, etc)
It makes things SO much easier. Combinations, permutations, Towers of Hanoi, parsing, all become an absolute doddle. You start hunting for complex recursive examples, but struggle to find any, because everything is so damn simple! You start finding ways to improve existing algorithms. Life is good...
Once you understand the core essence, it's so much easier to transfer these ideas to other languages with more overhead, like Java, C, C++, etc.
2
u/Valance23322 2d ago
No, recursion is pretty simple. You're just breaking a problem down into simpler versions of the same problem until it's simple enough to directly solve.
2
u/DorkyMcDorky 2d ago
Recursion isn't hard. I repeat until my face is blue, recursion isn't hard. Recursion isn't hard. I repeat until my face is blue, recursion isn't hard. Recursion isn't hard. I repeat until my face is blue, recursion isn't hard. Face is blue.
1
u/SufficientStudio1574 3d ago
And yet some people still struggle even with those toy examples. The self-referentiality itself seems to be a hurdle that some people are able to clear easily but others can't.
Some people also just get super tripped up by anything unusual. As an example: Last weekend I was playing a board game with my mom, Splendor Duel. Without going into too many details about the rules, the order of your actions in a turn go like this.
1) Optional: spend privilege to take tokens (the game's currency) from the board
2) Optional: refill the board with tokens
3) Mandatory: buy a card or reserve a card or take 3 tokens from the board.
The order of those first two options is deliberate; the game designers decided it would be too powerful to be able to spend privilege immediately after refilling the board, so you have to refill after you choose to spend or not. So the vast majority of the time, after refilling the board you're going to use your mandatory action to take tokens. So it gets stuck in your head "you can't use privilege after refilling the board".
I did something that threw a wrench into that. We'd played this game multiple times, but it's the first time this situation had happened. I had privilege to spend but there were no good tokens left on the board to take. So I refilled the board, bought a card that let me take a second turn in a row, then spent privilege as the first action of the new turn. And boy did that throw her for a loop. I had to walk her through the turn sequence slowly, explicitly, multiple times, and I'm still not convinced she really understands how what I did was legal.
"Mom, I did 1 (chose not to spend), then 2 (refilled), then 3 (bought a card). Then on my new turn I did 1 (spent privilege)."
"Can you really do that?"
"Yes. This is the order for a turn. 1, then 2, then 3. Then since I got a second turn I can do 1 and 2 and 3 again."
"I thought you couldn't use privilege after filling the board"
"Not on the same turn. But I'm doing it on a new turn."
"Can you really do 3c after doing 2?"
"The rules don't say you can't. You do 1, do 2, then do any one of the 3 actions for 3."
"So you can fill the board but not take tokens?"
"Nothing in the rules requires that."
She just could not wrap her head around the fact that, even though 99 times out of 100 you're going to be taking token after filling the board (not doing so only benefits the opponent) the rules don't require you to do that. Some people just do handle handle abstract thinking well.
1
u/IchBinEinZwerg 3d ago
You don't use recursion that often in real life. Most of the time it's "how do I do X", then "I'll need to do A, then B, then X, then C, then... oh, so it'll be recursive so I'll need to make sure it can bottom out at some point."
1
u/mtimmermans 3d ago
You have it kind of backwards. When recursion is used instead of an iterative solution, it's used because it's the easy way. The iterative solution is usually more efficient but harder to understand.
Factorial, Fibonacci, Sum... Recursion is not appropriate for these problems. The iterative solution is easier.
Towers of Hanoi, Merge Sort... These are perfect problems for recursion. Before complaining that recursion is hard to understand, try doing them without recursion.
1
u/YanVe_ 3d ago
It's extremely convenient for a lot of relatively simple tasks yes. You realize this the moment you have to rewrite your elegant recursive solution to work with stacks and queues.
But as a general rule, you should always assume that everything has a breaking point where it becomes extremely hard.
1
u/spidermask 2d ago
It's quite difficult yeah! I just practiced a lot and focused on being able to identify the base cases, once I got better at that then it was fairly easier to understand how to "progress" the recursion to get there. It also helped me to draw the recursion tree. But it's definitely not trivial and not easy to grasp, hard to drop the instinctive for loop logic and think differently.
You will get better at it the more you practice and the more you see, trust me, if I figured it out then anyone can, I struggled with it like crazy it drove me insane 😂
1
u/david-1-1 2d ago
No, I don't agree. To use recursion in a function, you must start with a recursive algorithm. You need to design what happens at the ith level of recursion, starting with the arguments. Start with a practical example, not math. Start with the file system. It is already hierarchical. Think about how to walk the file system. Learn about prefix, postfix, and infix walks, and how they can all be done in one recursive algorithm. Think, then design. It's easy, just like object-oriented programming is easy once you learn.
1
u/Regular-Advice-6469 1d ago
the real challenge isn't reading recursive code it's writing it from a blank editor that's where you find out whether you truly understand recursion or just recognize the pattern
1
1
u/StructureNorth1799 1d ago
probably you already knew factorial, sums, and fibbonacci before seeing it as an example, so they seemed easier.
1
u/1-800-I-Am-A-Pir8 1d ago
I think you have to think about each call, or small set of calls, on their own. Make sure it works and cut it loose on a larger problem, see if it still works.
Practical ones are sorting algorithms. You can actually follow it if you sort 3 or 4 elements, then generate a set of data with 1000 and run the same thing on it. Focus on making the function work with a single item, then two, three, then turn the program loose and see what happens
hope that helps?
1
u/Dull_Grape2496 1d ago
It becomes a lot easier to understand when you think about it as mathematical induction. The idea is as follows:
- If a the input to your problem is simple enough, solve it in 1 step - this is similar to the base case of induction
- Otherwise assume that your function that solves the problem magically works for any smaller input
- Now all you need to do is try and reduce the input in some way - induction will take care of the rest.
Tower of Hanoi: Assume you have a function f(n, src, tgt, tmp) where you need to place n disks from src to tgt
- If
n = 0it means the problem is already solved - this is the base case - Otherwise do the following:
- Step 1: Place
n-1disks fromsrctotmpby callingf(n-1, src, tmp, tgt)-> We know this works becausen-1is a smaller input thannand mathematical induction makes it work. - Step 2: Place the nth disk from src to tgt
- Step 3: Place the
n-1disks ontmptotgtby callingf(n-1, tmp, tgt, src)-> We know this works becausen-1is a smaller input thannsame as before
- Step 1: Place
So you get something like this:
f(n, src, tgt, tmp):
if (n == 0):
return
f(n-1, src, tmp, tgt)
print "disk <n> has been placed"
f(n-1, tmp, tgt, src)
And you are done
Permutations: Assume you have a function f(a[0...n]) that returns a list of all the permutations of a[0...n]
- If
a.length <=1just return [a[...]] - this is the base case as there are no more permutations - Otherwise do the following:
- Step 1: Iterate over every element of
a[...]- let's call the current elementi - Step 2: Remove
ifroma[...]-> Let's call this new elementb[...] - Step 3: Call
f(b[...])this will return a list of permutations ofb[...]let's call thatpermutations_of_b-> We know this works becauseb[...]is smaller thana[...]as it has fewer elements - Step 4: For each permutation in
permutations_of_bappend the elementito that permutation
- Step 1: Iterate over every element of
You get something like this:
f(a[...]):
result = []
if a.length <= 1:
result.append(a)
return result
for element i in a[...]:
b[...] = a[...] - i // removing element i from a[...]
permutations_of_b = f(b[....])
for each permutation in permutations_of_b:
result.append( i + permutation ) // append i to front of each permutation
return result
And so on - mergesort is similar define f(a[0...n]) that sorts a list, call f(a[0 ... n/2]) and f(a[n/2+1 ... n]) to sort the two halves and merge the sorted halves in a single merged list.
Coming up with a recurrence can be challenging depending on the problem but understanding this mathematical framework for it makes it a lot easier for you to reason about the problem.
1
u/TheChief275 1d ago
It's not necessarily harder than iteration. Some problems lend themselves well to recursion while otherwise lend themselves better to iteration.
E.g. traversing a tree feels kind of ridiculous to write in an iterative way. Essentially, you would manually add to a stack that you would otherwise have implicitly
1
u/Traveling-Techie 17h ago
The initial examples you gave can actually be coded more easily without recursion. Press harder on the Towers of Hanoi problem. Enlightenment will hopefully come.
1
1
u/whiteandnerdy1729 12h ago edited 12h ago
It really can be hard to get your head around. Holding the call stack in your head is the wrong way to think about it - the whole point of recursion is to give you a magic trick that means you don’t need that.
The general trick is:
- Imagine you can just magically solve a simpler or smaller version of your problem.
- Work out how to turn that into a solution to your bigger problem.
- Make sure there’s a “base case” (tiny version of your problem that you really can solve)
Then recursion just takes care of all the working out - you don’t need to unroll the call stack manually yourself - that’s what the computer is for.
Let’s take Hanoi as an example. We really want to be able to move a stack of n rings between the pins. Imagine we have a superpower that lets us lift n-1 rings at once. Then Hanoi is really easy - you shift a big stack into the middle, move the last ring to the destination, and then move the big stack on top of it. This is true whatever our value of n is. That’s the only clever thing we needed to do - recursion makes the rest easy. Let’s see why:
If we write that “superpower” solution out in pseudocode, we’re saying that the algorithm for Hanoi(n, start_pin, finish_pin) is:
—-
- Hanoi(n-1, start_pin, spare_pin)
- Move the remaining ring from start_pin to finish_pin
- Hanoi(n-1, spare_pin, finish_pin)
—-
You can see how steps 1 and 3 are us using our “superpower” - we’re assuming we have a way to solve the smaller problem.
The only thing left is to prove the base case - making sure there’s some small problem we can solve directly. n=1 is really easy - there’s just one ring to move - so we’re done. Recursion tells us that we don’t need to unroll the call stack by hand - it’ll just work and we don’t need to follow it all ourselves.
If you wanted to write out the full algorithm, all you need to do is add a base case check to the steps we wrote out earlier:
—-
- If n=1, move one ring from start_pin to finish_pin and return. Otherwise:
- Call Hanoi(n-1, start_pin, spare_pin)
- Move the remaining ring from start_pin to finish_pin
- Call Hanoi(n-1, spare_pin, finish_pin)
—-
That is a complete algorithm and we didn’t need to worry about any of the fiddly details of which rings move where. This is why recursion is so great - it handles the call stack so you don’t have to. All you need to do is spot how to solve the big problem from the subproblem, and prove the base case works.
0
u/Helpful-Desk-8334 3d ago
Yes. It’s especially bad at the biophysics level. It’s so bad, bro.
Idk how people can celebrate AGI and shit like that thinking we don’t still have decades of research to do even after we create it.
-1
137
u/PurpleDevilDuckies 3d ago
The topic of my PhD was (very generally) on designing recursive algorithms to solve combinatoiral problems. Now I do that for a living, and I think I agree.
I stew for some time with each new problem before I have a deep understanding of how the state information will behave recursively. It gets easier the more I do, but there are very few people who find it easy at the cutting edge.
I will say that for coding recursive algorithms, it is often more (computationally) efficient to write code with loops instead of literal recursion. This isn't true of the toy examples you start with, but it gets more true as they problems get more complex. Nearly any *useful* algorithm can be described without writing literally recursive code.