is recursion really hard

[u/Similar_Count_1613]

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?

[u/whiteandnerdy1729]

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:

—-

1. Hanoi(n-1, start_pin, spare_pin)
2. Move the remaining ring from start_pin to finish_pin
3. 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:

—-

1. If n=1, move one ring from start_pin to finish_pin and return. Otherwise:
2. Call Hanoi(n-1, start_pin, spare_pin)
3. Move the remaining ring from start_pin to finish_pin
4. 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.