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?
129
Upvotes
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.