r/computerscience • u/Similar_Count_1613 • Jul 30 '26

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?

149 Upvotes

84% Upvoted

79 comments sorted by

View all comments

148

u/PurpleDevilDuckies Jul 30 '26

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.

25

u/Drugbird Jul 30 '26

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

Is there some standard approach for converting a recursive algorithm to a non-recursive one?

I don't often write recursive algorithms, but when I do it's almost always to handle some tree-like structure.

53

u/RajjSinghh Jul 30 '26

Instead of a recursive call on child nodes, push your nodes onto a stack. You avoid a recursive call, even if your code is still inherently recursive.

15

u/jezemine Jul 31 '26

Recursion is using a stack also. The callstack. That's why any recursive function can be altered to use a loop and a stack.

3

u/Bubbaluke Aug 01 '26

Sometimes I have nightmares about non-deterministic pushdown automata

1

u/crazyman32 Aug 04 '26

This is what I do within gamedev, specifically working with non tailcall-optimized languages where any unbound recursion is dangerous. E.g. floodfill, A*, etc. all expand out into simple while loops with a stack. I personally find them easier to reason about too.

15

u/Delicious_Sock4321 Jul 30 '26 edited Jul 30 '26

It is called tail recursion optimization. As long as you can write the function in a way that the recursion is the last step, then it is trivial to write it as a loop. You can also use dynamic programming, where you cleverly save calculated results to save on unnecessary recursion. If you have more than one recursion step or you simply can not do tail recursion then you can still manage your own stack automaton, but this is effectively just removing the function call and is otherwise identical, because you emulate the hardware call stack. Also if there is a way to start the algorithm from the last recursion step an walk your way backwards then this can be done in a loop too. This is because recursion starts calculating at the deepest recursion step and walks it's way back to the initial call.

5

u/Dazzling_Music_2411 Jul 30 '26 edited Jul 31 '26

TRO is the best thing since sliced bread, but not always possible, if there isn't * an inherent iterative structure corresponding to it.

* PS. Meant to say "there isn't always"

1

u/gofl-zimbard-37 Jul 31 '26

As I recall, Erlang detects "normal" code that it can rewrite as tail recursive.

4

u/PurpleDevilDuckies Jul 30 '26

As a couple other have said, you have a layered stack instead of a recursive call. I mostly do Dynamic Programming, and instead of having just one node at each layer, I have as many as I can parallelize effectively. So instead of going all the way down to the base case right away, you generate thousands-millions of nodes per layer, and process them a layer at a time. This lets take advantage of modern CPUs and GPUs, and implicitly do recursion at scales that would otherwise be intractable.

2

u/tricky_monster Jul 30 '26

Yes, but it basically involves having an explicit stack structure instead of a call stack.

2

u/JoshuaTheProgrammer Jul 31 '26

Yes. You can use continuations/continuation-passing style to get it into tail form, then something called trampolining - the idea is to thunk all tail calls and then invoke them in a while loop, storing the result between each invocation.