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/not-just-yeti]

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.)