3 ms·
Lots of problems have vastly simpler recursive solutions. Try putting a recursive descent parser into a loop. Plenty of tree walking/formatting/analyzing algori
by ChrisLomont 5y ago
Lots of problems have vastly simpler recursive solutions. Try putting a recursive descent parser into a loop. Plenty of tree walking/formatting/analyzing algorithms are much cleaner using recursion. Recursively walking directory structures is cleaner using recursion. Many puzzles, such as Tower of Hanoi, are cleaner with recursion. Many sort algorithms, like merge sort, quicksort, etc., are cleaner with recursion. I could find plenty more algorithms where recursion makes the solution cleaner, simpler (hence less error prone), and sometimes even faster to execute.
And some algorithms use mutual recursion to solve problems - often putting those into a non-recursive formulation results in incredibly messy code. Mutual recursion is powerful enough that F# (among others) added an entire keyword to the language simply to support it.
And since many languages do proper tail recursion, there is no penalty for using it properly.
- ncmncm 5y agoIn CS, you encounter lots of problems that are naturally solved by recursion not because such problems are especially common, but because they are favorites of CS professors. Language parsers do a lot of recursion because the languages we invent are invented by CS people who like problems that can be solved that way, and because language itself is one that lends itself to that. It is hard to tease out which recursions we find because professors just like it, and which ones real-world problems demand. Many commonly cited as the latter turn out, on close examination, to be the former.
- titzer 5y ago> but because they are favorites of CS professors. I work on compilers and compilers are full of graphs. Graphs typically have a lot of algorithms that are naturally recursive. It's not because of some theoretical fetish.
- ncmncm 5y agoBut CS professors love graph problems. So, it's not so easy to say.
- ChrisLomont 5y ago>It is hard to tease out which recursions we find because professors just like it, and which ones real-world problems demand As someone that works on real world problems all over the spectrum (google my name), I can say with extensive expertise that a significant number of problems are vastly better solved with recursion. I didn't cite most of the list above because a textbook said so. It's because I use and design algorithms all over the map in all sorts of languages for a living, precisely for real world problems. I take it you don't use this tool when appropriate do you?
- ncmncm 5y agoIn fact I always do.
- ChrisLomont 5y agoYet you've filled this thread with demonstrable fallacies regarding performance, overflowing stacks, and inability to see cleaner code. Odd.
- ncmncm 5y agoIn fact, I wrote none of those. I don't know what "inability to see cleaner code" even means, if anything, so I could not have made claims about it. But I wonder, do you really believe that overflowing one's stack is, universally, not possible?
- ChrisLomont 5y ago>In fact, I wrote none of those A quote from you: "You encounter it in the recursive case, painfully, when your stack overflows." And we're done.