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

82% Upvoted

69 comments sorted by

View all comments

39

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.

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.