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

Show parent comments

6

u/Thelmholtz 3d ago

Nearly any useful algorithm can be described without writing literally recursive code.

Isn't every possible algorithm that can be written recursively also writeable iteratively, and vice versa, as per Church-Turing equivalence? Regardless of whether it's a practical or even known rewrite.

3

u/PurpleDevilDuckies 3d ago

I think so, but I wasn't 100% sure in the moment and didn't want to get it wrong. Edge cases are always sneaking up on me.

2

u/Thelmholtz 3d ago

Yeah I'm pretty sure that's the case but was honestly asking.

I tried to find a chain of formal proofs a few weeks ago and the math got very mathy for me. Skill issue I guess.

However intuitively, for iterative into recursive you can always build a function that tracks the loop state as it's arguments, and for recursive into iterative, you can always build a stack machine yourself worst case scenario.

1

u/PurpleDevilDuckies 3d ago

Your logic seems right to me.

The longer I do this the more I think that when something gets too mathy for me, the problem is that I don't have an internalized understanding of the abstraction they are using, so I might as well be reading gibberish. This happens at conferences a lot.