4 ms·
Yeah, every time I've written I recursive algorithm in the past, I've eventually had to come back and reimplement it as iterative. It's such that I no longer st
by moron4hire 6y ago
Yeah, every time I've written I recursive algorithm in the past, I've eventually had to come back and reimplement it as iterative. It's such that I no longer start the recursive approach anymore and go straight to iterative.
The iterative solution is better in every regard. The state transitions are easier to see, and the sub procedures are easier to identify and split up, if necessary.
I have a degree in Computer Science, I did extremely well in that degree program, and I understand algorithms very well. I don't get the fascination with recursion in CS theory. It's just hiding state on the stack frame. That's why it's such a terrible tool, not just for engineering, but for teaching as well. Every recursive solution has an iterative solution, even if it's just tossing your state into a Stack data structure you manage yourself on the heap. You'd think you'd want to call that out for students.
- dehrmann 6y agoI only use recursion where it makes sense and I can guarantee O(log n) runs. Unbalanced tree? Iterate. Large graph? BFS. That said, I agree with another comment here that you're more likely to have a bug code where you're maintaining a stack by hand. Recursion is easier when it's the best fit for the problem.
- moron4hire 6y agoFundamentally disagree. Any bugs in the iterative approach are likely to be found during development on even the simplest of synthetic test data sets. But the recursive approach has a gigantic bug lying in wait for you to run more data than you originally anticipated: the stack overflow.
- dehrmann 6y agoI used to proctor an on-site laptop coding test where part of the solution involved traversing a large digraph. Maybe 50% of candidates could do it on their own without a bug in 45 minutes. 15% of candidates knocked it out by the halfway mark. Not that this is the best use of recursion--both implementations still need to track visited nodes.
- andi999 6y agoThe Forth is not strong with this one... (I am fully on your side btw)
- xkriva11 6y agoColorForth mostly forces you to use recursion for loops
- imoverclocked 6y agoSome languages don’t have loops but rather have very good tail-recursive semantics. In that case, nothing is hiding in the stack. Talking about loops vs recursion is interesting but it feels kinda like salt vs pepper to me. I like both and use both where appropriate. While we are on the topic of similarly misused constructs, .stream() pipelines in Java are often clear and concise but as they get longer and hide more stuff in the stream, a loop would make far more sense and provide a much smaller runtime complexity. Often, people will aspire to create “beautiful” code where they relate recursion/loops/streams/etc as something beautiful. In that vein, I don’t really care if code is “ugly” but I do care if it’s unmaintainable, needlessly slow or accidentally complex.
- moron4hire 6y agoYeah, one of my last favorite phrases is "elegant code". "Elegance" is an attribute I'd assign to a dinner party, not work.
- thebigspacefuck 6y agoMath heads frequently use the term for proofs. I see it as carry over
- magicalhippo 6y agoI use recursion fairly often, and I almost never come back and reimplement it as iterative. Mostly because I know my data structures are bounded, and the thing I'm writing isn't terribly performance sensitive. The iterative solution is in the language we use a lot more verbose. I'd have to create a separate type to hold any parameters if there's more than one and I'd have to make my own stack of that type. So for most things I just go for plain old recursion.