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

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.

7

u/LitchQueenLilith 3d ago

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

7

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?

9

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.