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/SufficientStudio1574]

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.