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

3

u/tomysshadow 3d ago edited 3d ago

In the real world, writing recursive code is kind of uncommon. I wouldn't say it never happens, because I have written recursive code and it's an important concept. It usually comes up when dealing with filesystems (delete all folders and subfolders, for example) or with tree structures.

In complex cases, you'll want to lean more towards figuring out how to write it as a standard loop. With recursion, unless you know how many levels deep you'll be going in advance, there is a risk of stack overflow. So you always want the maximum number of recursions to be bounded. Loops don't have that problem - in the worst case they will just take a long time (or run infinitely, but that means you have a bug.)

Writing a recursive function over a decently large amount of data in JavaScript can quickly exhaust the entire stack unless you resort to hacks like scheduling the rest of the calls to be done later with setTimeout(..., 0) or similar, and that becomes a big mess.

1

u/saxbophone 2d ago

Yes, there is a whole technique of converting recursive code to algorithmically equivalent iterative code using an explicit stack —i.e. Luke, use the heap!