6 ms·

I don't think you represent the average coder. I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit

I don't think you represent the average coder. I'm willing to bet most people if shown 10 recursive and 10 iterative solutions to the same problems would admit the iterative approach is more intuitive. Especially since with a for loop you can control the number of iterations which has a number of optimization benefits. Now if its just while loops vs recursive then there's not much of a difference, however that is not the case.

deleted 8y ago
[deleted]
deleted 8y ago
[deleted]
FractalLP 8y ago
Agreed. HackerNews has a greater than average amount of developers that use Haskell, F#, OCaml, Scheme, and other languages which heavily promote recursion. I'm not sure if I personally find iteration easier because I learned it first, it matches my brain better, or if it is indeed easier for most of the population.
joefkelley 8y ago
You might be able to trace the execution of the iterative code more easily, but in my experience it is often much less clear why that produces the correct result and how that code was written in the first place. Take a look at the wikipedia page for computing Levenshtein distance: https://en.wikipedia.org/wiki/Levenshtein_distance#Computing_Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance#Computing... The recursive version needs barely any explanation. But ask me to carry it out by hand and I'm sure I'll pretty quickly get lost. The iterative version needs a lot more explanation for why it is the way it is, but I also think I could carry it out on paper quite easily.
- ghettoimp 8y ago
  Very much agree. If you are working on any kind of tree structure, graph, parse tree, etc., recursion can be really beautiful and clear. My theory: folks like iteration because 90% of the "for" loops they write are really just "foreach".
  - bogomipz 8y ago
    >"folks like iteration because 90% of the "for" loops they write are really just "foreach"." I didn't understand this comment. What do you mean by "for vs foreach."? Can you elaborate?
    - bkdonline 8y ago
      I guess the foreach is where each iteration has independent operation, vs a generic for loop where this iteration depends on result of the previous iterations.
- blackflame7000 8y ago
  I mean if you label all your variables i,j, and k and use minimal formatting or bracketing then I see your point it is harder to read. Whats complicated about an iteration. If it works properly after the first one chances are it will continue to work for the millionth one. If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. Conversely, you must always make sure the stopping condition and all base cases are met during recursion. Forget one corner base case and you got a rare production bug.
  - kolpa 8y ago
    In an iterative solution, you have to get your loop conditions correct, and you have to create a bunch of inputs before you know how you are going to use them, sort of a "solution in search of the problem". Recursion takes a problem and expresses it terms of similar, but smaller, unsolved problems, unless you can solve it directly (base case). It's a "problem in search of a solution", that always makes progress (unless you have a bad algorithm, as always). If a recursive solution works on a small input, it will work on a big input. If you missed a base case, you'll see it immediately because trivial (literally!) input will make your solution fail to terminate. In production, the main problem with recursion is stack size limits (or more generally memory limits) if you can't/don't use tail-call elimination.
  - throwaway37585 8y ago
    > Whats complicated about an iteration What’s complicated about a recursion? > If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. > Conversely, you must always make sure the stopping condition and all base cases are met during recursion. You seem to be applying a double standard here. > Forget one corner base case and you got a rare production bug. Base cases are usually much easier to reason about.
    - blackflame7000 8y ago
      Then why does NASA consider it unsafe for mission critical code? How about unknown potential stack size? How about factoring a large number with recursion? Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet https://www.reddit.com/r/programming/comments/3dnsh1/nasas_ten_coding_commandments/ https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...
nordsieck 8y ago
It really depends on the kind of problem. For example, recursive solutions to linked-list/tree/graph problems are typically substantially easier to understand than their iterative counterparts, in large part because the data structures themselves are recursively defined.
drb91 8y ago
It's only more intuitive to see the shape of the serial execution. That same property makes it more difficult to prove qualities about the code (say, correctness) because you need to keep track of state in your head as you trace through the program, rather than encoding it structurally as you would with a recursive solution. So, intuitive is not so valuable unless you get correctness out of it.
zodiac 8y ago
Depends on the problem. Some problems have very explicit recursive structure (eg http://rosettacode.org/wiki/Arithmetic_evaluation http://rosettacode.org/wiki/Arithmetic_evaluation) such that an iterative solution is more "unnatural". Not saying that most problems are like that, just that this shows it depends on the problem.
barrkel 8y ago
Most recursive functions have a tree structure, either in the control flow or data flow. For loops don't really cut it; you minimally need auxiliary storage to track which branch you're currently on for every ancestor level, either explicitly by pushing indexes or structures onto a stack or queue, or implicitly with a work stack or queue. That's a bunch of accounting in an iterative solution you don't need with a recursive solution. The iterative solution will end up harder to read as a result. It'll also be a lot harder to reason about if the tree-like structure of the code is obscured. If you need to return values for processing each child, and integrate them at the parent, then your solution gets tougher to reason about, as there's an ordering constraint and a dependency. Recursion doesn't come up super often in most domains, but it's not rare. E.g. doing anything non-trivial with the DOM in a web front end, parsing an XML or JSON document, etc.

deleted 8y ago

[deleted]

deleted 8y ago

[deleted]

FractalLP 8y ago

Agreed. HackerNews has a greater than average amount of developers that use Haskell, F#, OCaml, Scheme, and other languages which heavily promote recursion. I'm not sure if I personally find iteration easier because I learned it first, it matches my brain better, or if it is indeed easier for most of the population.

joefkelley 8y ago

You might be able to trace the execution of the iterative code more easily, but in my experience it is often much less clear why that produces the correct result and how that code was written in the first place. Take a look at the wikipedia page for computing Levenshtein distance: https://en.wikipedia.org/wiki/Levenshtein_distance#Computing_Levenshtein_distance https://en.wikipedia.org/wiki/Levenshtein_distance#Computing... The recursive version needs barely any explanation. But ask me to carry it out by hand and I'm sure I'll pretty quickly get lost. The iterative version needs a lot more explanation for why it is the way it is, but I also think I could carry it out on paper quite easily.

ghettoimp 8y ago
Very much agree. If you are working on any kind of tree structure, graph, parse tree, etc., recursion can be really beautiful and clear. My theory: folks like iteration because 90% of the "for" loops they write are really just "foreach".
- bogomipz 8y ago
  >"folks like iteration because 90% of the "for" loops they write are really just "foreach"." I didn't understand this comment. What do you mean by "for vs foreach."? Can you elaborate?
  - bkdonline 8y ago
    I guess the foreach is where each iteration has independent operation, vs a generic for loop where this iteration depends on result of the previous iterations.
blackflame7000 8y ago
I mean if you label all your variables i,j, and k and use minimal formatting or bracketing then I see your point it is harder to read. Whats complicated about an iteration. If it works properly after the first one chances are it will continue to work for the millionth one. If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. Conversely, you must always make sure the stopping condition and all base cases are met during recursion. Forget one corner base case and you got a rare production bug.
- kolpa 8y ago
  In an iterative solution, you have to get your loop conditions correct, and you have to create a bunch of inputs before you know how you are going to use them, sort of a "solution in search of the problem". Recursion takes a problem and expresses it terms of similar, but smaller, unsolved problems, unless you can solve it directly (base case). It's a "problem in search of a solution", that always makes progress (unless you have a bad algorithm, as always). If a recursive solution works on a small input, it will work on a big input. If you missed a base case, you'll see it immediately because trivial (literally!) input will make your solution fail to terminate. In production, the main problem with recursion is stack size limits (or more generally memory limits) if you can't/don't use tail-call elimination.
- throwaway37585 8y ago
  > Whats complicated about an iteration What’s complicated about a recursion? > If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. > Conversely, you must always make sure the stopping condition and all base cases are met during recursion. You seem to be applying a double standard here. > Forget one corner base case and you got a rare production bug. Base cases are usually much easier to reason about.
  - blackflame7000 8y ago
    Then why does NASA consider it unsafe for mission critical code? How about unknown potential stack size? How about factoring a large number with recursion? Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet https://www.reddit.com/r/programming/comments/3dnsh1/nasas_ten_coding_commandments/ https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...

nordsieck 8y ago

It really depends on the kind of problem. For example, recursive solutions to linked-list/tree/graph problems are typically substantially easier to understand than their iterative counterparts, in large part because the data structures themselves are recursively defined.

drb91 8y ago

It's only more intuitive to see the shape of the serial execution. That same property makes it more difficult to prove qualities about the code (say, correctness) because you need to keep track of state in your head as you trace through the program, rather than encoding it structurally as you would with a recursive solution. So, intuitive is not so valuable unless you get correctness out of it.

zodiac 8y ago

Depends on the problem. Some problems have very explicit recursive structure (eg http://rosettacode.org/wiki/Arithmetic_evaluation http://rosettacode.org/wiki/Arithmetic_evaluation) such that an iterative solution is more "unnatural". Not saying that most problems are like that, just that this shows it depends on the problem.

barrkel 8y ago

Most recursive functions have a tree structure, either in the control flow or data flow. For loops don't really cut it; you minimally need auxiliary storage to track which branch you're currently on for every ancestor level, either explicitly by pushing indexes or structures onto a stack or queue, or implicitly with a work stack or queue. That's a bunch of accounting in an iterative solution you don't need with a recursive solution. The iterative solution will end up harder to read as a result. It'll also be a lot harder to reason about if the tree-like structure of the code is obscured. If you need to return values for processing each child, and integrate them at the parent, then your solution gets tougher to reason about, as there's an ordering constraint and a dependency. Recursion doesn't come up super often in most domains, but it's not rare. E.g. doing anything non-trivial with the DOM in a web front end, parsing an XML or JSON document, etc.