7 ms·
Is recursion really worth the loss of clarity? Almost always no. The more clever you are in your code, the less likely anyone will ever see it (or want to).
by blackflame7000 8y ago
Is recursion really worth the loss of clarity? Almost always no. The more clever you are in your code, the less likely anyone will ever see it (or want to).
- darzu 8y agoWhy are you assuming that the recursive solution is less clear?
- blackflame7000 8y agoExperience, tells me so. To be fair some items like Fibonacci numbers are probably equally as clear.
- deleted 8y ago[deleted]
- danmg 8y agoDivide an conquer type algorithms usually lend themselves to naive recursive solutions more often than not. DP usually requires you to find that solution and find some clever relationships that allow you to build up the final solution from the bottom up.
- blackflame7000 8y agoSure there are some problems that lend themselves nicely I already said as much. But in general for an INTERVIEW problem, it as a poor skill to dwell on or even bother testing for since real-world coding is simply not done that way or God forbid what might happen when someone not as capable (but cheaper or younger) has to take over your code base.
- danmg 8y agoWe're talking about ACM style search problems that are used for interviews, and not about iterating over an array recursively. For these, the recursive formulation is the naive and inefficient way of solving them.
- kolpa 8y agoIf you systematically analyze it, you don't need to be clever on a per-problem basis. Every recursive solution can me methodically converted to DP.
- danmg 8y agoYes, it's a form of pattern recognition. You can get very good at it and do it mechanically, just like solving integrals. You can spend a lot of time getting very good at them, or you can just use memorization/rsolve just like you can just use maple or evaluate them numerically for integrals.
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- algo646464 8y agoAll dynamic programming algorithms are recursive. They are essentially a (constructive) proof by induction. For clarity, perhaps one can include a "proof of correctness" of the algorithm in the comments.
- jacquesm 8y agoRecursion is usually clearer that iterative because it assigns names to the work being done. I find that much easier to read. Better yet: when you can state your cases separately. That's even more readable.
- blackflame7000 8y agoI 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 agoAgreed. 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 agoYou 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.
- Silfen 8y agoIt depends on the particulars of a problem, but structural recursion is often substantially clearer. One reason is that it enables more abstract reasoning about the behavior of an algorithm. You can reason like you would for an induction proof, instead of mentally executing steps in a loop (denotational vs. operational).
- oldandtired 8y agoThere are problems that have clearer solutions when expressed as recursive. There are problems that have clearer solutions when expressed as iterative. Having both tools in your toolbox and knowing when to use each is part and parcel of developing yourself as a craftsman or craftswomen programmer. In addition, being able to know when to use memoing in producing your solution is another tool to be put in your toolbox. Yes, every recursive function has an iterative solution, but the iterative solution can be far more complex. The best example of this is that lovely little function - Ackermann-Peter function. The recursive version is just a few lines long. The iterative version is quite a few pages long. There are specific schemas in which the recursive form should be rewritten as an iterative solution. You can find these detailed in such old gems of books like "Algorithms + Data Structures = Programs".