4 ms·

Just try implementing merge sort to see how recursion results in simpler code. Cannot imagine how a stack data structure and a while loop is simpler than two re

by newen 6y ago

Just try implementing merge sort to see how recursion results in simpler code. Cannot imagine how a stack data structure and a while loop is simpler than two recursive calls. I don’t know, maybe this is just a new programmer meme. The number of programmers have supposedly doubled every five years, so I imagine internet programming discussion would be dominated by new programmers, and would have been dominated by new programmers for the last several decades.

skybrian 6y ago
Whether it's simpler depends on the problem. There was a programming interview question I used to use where you'd typically build a tree and print it out. I would warn people against trying to build the tree recursively because it never went well. (Printing it out was fine.) I think part of it was that to use recursion properly in this case, you'd have to return multiple values, and that complicated things, particularly if they were using a language like Java where it's not built-in.
- Jtsummers 6y ago
  Why would building a tree require returning multiple values? Was this something specific to your problem statement? Typical tree insert algorithms are usually easily expressed recursively (though since they can be tail recursive, iterative versions are usually also easy to write).
  - skybrian 6y ago
    It was effectively a parsing problem. When building a tree recursively, it's natural to return the finished subtree, but more information was needed to keep track of what gets parsed next. You would need to return both the result and the start of the unparsed input. In imperative languages, parsers are often written using the fields of an object or struct to hold the parser state. But if you're just writing a single function then it becomes more natural to keep the parser state in local variables, and recursion means you don't have easy access to it.
    - Jtsummers 6y ago
      That makes sense, thanks.
- xupybd 6y ago
  >>Whether it's simpler depends on the problem. I couldn't agree more. One down side of recursion can be that if you need to refactor you might find recursion is no longer the better solution. Unwinding that can be a pain.

by newen 6y ago

skybrian 6y ago

Whether it's simpler depends on the problem. There was a programming interview question I used to use where you'd typically build a tree and print it out. I would warn people against trying to build the tree recursively because it never went well. (Printing it out was fine.) I think part of it was that to use recursion properly in this case, you'd have to return multiple values, and that complicated things, particularly if they were using a language like Java where it's not built-in.

Jtsummers 6y ago
Why would building a tree require returning multiple values? Was this something specific to your problem statement? Typical tree insert algorithms are usually easily expressed recursively (though since they can be tail recursive, iterative versions are usually also easy to write).
- skybrian 6y ago
  It was effectively a parsing problem. When building a tree recursively, it's natural to return the finished subtree, but more information was needed to keep track of what gets parsed next. You would need to return both the result and the start of the unparsed input. In imperative languages, parsers are often written using the fields of an object or struct to hold the parser state. But if you're just writing a single function then it becomes more natural to keep the parser state in local variables, and recursion means you don't have easy access to it.
  - Jtsummers 6y ago
    That makes sense, thanks.
xupybd 6y ago
>>Whether it's simpler depends on the problem. I couldn't agree more. One down side of recursion can be that if you need to refactor you might find recursion is no longer the better solution. Unwinding that can be a pain.