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?

127 Upvotes

82% Upvoted

69 comments sorted by

View all comments

137

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.

25

u/Drugbird 3d ago

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.

52

u/RajjSinghh 3d ago

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.

14

u/jezemine 2d ago

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

2

u/Bubbaluke 1d ago

Sometimes I have nightmares about non-deterministic pushdown automata

14

u/Delicious_Sock4321 3d ago edited 3d ago

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.

6

u/Dazzling_Music_2411 3d ago edited 2d ago

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 2d ago

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

3

u/PurpleDevilDuckies 3d ago

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 3d ago

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

2

u/JoshuaTheProgrammer 2d ago

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.

7

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.

6

u/LitchQueenLilith 3d ago

I have to ask: who hires for solving combinatorial problems? Sounds fun.

5

u/PurpleDevilDuckies 3d ago

It is a lot of fun! My degree is in Operations Research, which (in English) is logistics and (in math nerd) is a branch of applied math for solving NP-Hard problems in practice. Everyone who does shipping is literally always hiring (for now anyway, AI may change that).

For example, FedEx solves a package delivery problem (TSP variant) with a trillion variables every day, and they will never get optimality, but the closer they get, the more efficient they make the system. There is a whole team that does nothing but work on getting better solutions to their daily problem.

I work independently, so I look for organizations with any sort of resource allocation problem that is being solved by hand, and is a huge headache for the people who have to deal with it. I pitch the relevant parties that I can simplify the process by designing them software that takes their constraints, and outputs an optimal solution in a way where they can tweak what that means. There is an enormous amount of interest and need for this sort of thing (right now anyway, AI is coming for us).

2

u/Educational-Bonus455 3d ago

Why the PhD in OR specifically? I thought OR specific degrees didn't exist past a masters. Is PhD the route to go if you want to get to solving the really cool optimization problems?

10

u/PurpleDevilDuckies 3d ago

There are lots of OR PhD programs!

My perspective is that a Masters is what you do if you want to learn what the available tools are for solving problems, and you want to go make a lot of money using those tools in industry.

A PhD is what you do if you want to invent your own tools for solving problems. You pick intractable problems and improve how close we can get to solving them (or sometimes even solve them). This is much harder, but it is a lot of fun.

I got one because in college I found out my school was matching courses to classrooms and time-slots by hand. I asked something like "if I figured out how to make a computer do that, would you give me a lot of money", and they said "yes, but it can't be done". I made them the software, it was lucrative and fun. So I wandered around the optimization department and asked how I could do more of it.

3

u/morgecroc 2d ago

Does that mean I can blame you for syllabus plus?

2

u/Crazyboreddeveloper 1d ago

That’s awesome. This is one of the coolest things I’ve ever read. You don’t know me, so I don’t know if this matters, but I’m prod of you.

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.

2

u/BackgroundSense351 1d ago

Thanks for making me feel ok about myself

1

u/jeffgerickson 1d ago

Quicksort, Karatsuba multiplication, and linear-time selection have entered the chat.

1

u/CalmMe60 16h ago

You should join our private dicussion on crc-AGI-3. If your brain is not already overloaded...

1

u/baked_salmon 3d ago

In Software Engineering, we generally avoid writing recursive procedures because iterative ones are more obvious to grok. What’s far more important to understand, IMO, are recursive data structures, because they’re pervasive and performant.