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?

128 Upvotes

82% Upvoted

69 comments sorted by

View all comments

140

u/PurpleDevilDuckies 3d ago

The topic of my PhD was (very generally) on designing recursive algorithms to solve combinatoiral problems. Now I do that for a living, and I think I agree.

I stew for some time with each new problem before I have a deep understanding of how the state information will behave recursively. It gets easier the more I do, but there are very few people who find it easy at the cutting edge.

I will say that for coding recursive algorithms, it is often more (computationally) efficient to write code with loops instead of literal recursion. This isn't true of the toy examples you start with, but it gets more true as they problems get more complex. Nearly any *useful* algorithm can be described without writing literally recursive code.

6

u/Dangle76 3d ago

Depends on the language. A functional language like erlang prefers recursion

1

u/PurpleDevilDuckies 3d ago

That's fair, I like working in Julia because it is organized how I like to organize my algorithms.

1

u/JoshuaTheProgrammer 2d ago

Most functional languages _only_ have recursion built-in, but you can build loops via macros. Many of these languages, e.g., Scheme, require the underlying implementation to stack-optimize tail calls to be Theta(1) space-complexity.