5 ms·
No, you may have to think about it a little more, especially when first getting acquainted with recursion, but the recursive solution is likely to be less compl
by jackfoxy 11y ago
No, you may have to think about it a little more, especially when first getting acquainted with recursion, but the recursive solution is likely to be less complex and more robust. It's the repetition of a simpler idea, and so there are fewer ways to screw-up the implementation.
- xyzzy4 11y agoI disagree. Recursion makes a stack trace that should be 10 functions deep into one that's 1000 functions. It's difficult to debug and follow the code around, or even to understand the code if someone else wrote it. Also recursive functions tend to spiral out of control and have ridiculous exponential run times.
- eru 11y ago> I disagree. Recursion makes a stack trace that should be 10 functions deep into one that's 1000 functions. Recursion has nothing to do with stack traces. Stack are one way to implement some version of recursion in functions. Some other versions of recursion in functions can be implemented with loops. And, of course, not only function can be recursive, but data structures as well. (And a few other things.) You can traverse these data structures any way you feel like. > It's difficult to debug and follow the code around, or even to understand the code if someone else wrote it. I have that problem with loops (and mutation) much more than with recursion. Different things make different people's heads hurt. > Also recursive functions tend to spiral out of control and have ridiculous exponential run times. Oh, that's an artifact of how you've been taught (or self-taught). Loops are a special case that only works well for simple tasks. Recursion is more general and can express the simple case in a simple way. Of course, if you only reach for recursion in the complicated cases, all uses of recursion you see will be complicated. Simple observation bias.
- eru 11y agoPS Another way to implement function calls (and thus recursion) is transformation into continuation passing style.
- Gratsby 11y agoYou sound like someone who went down the Haskell rat hole. As someone who also has visited that dark and twisted land... I completely agree with you (every post in this thread). I don't think I ever once experienced the supposed benefits.
- mmcclure 11y agoCorrect me if I'm wrong, but aren't both of these concerns largely covered by any language that has tail call optimization (basically any functional language)?
- eru 11y agoSome of them. If you have exponential run times, I don't think tail call optimization would help you. Of course, that claim with the exponential run time in the first place is ludicrous: sure, you'll have a hard time implementing the Ackermann function with loops. But that's a problem with loops, not with function calls. I say function calls here, because recursion in function is just a special case of function calls. You gotta have functions in a modern language in any case, so recursion comes for free. No need to introduce another concept like loops and clutter up your language.
- gvargas 11y agoTrue to a degree. Languages that promote the use of recursion often implement tail call optimization so if the process is an iterative recursive process (all state is captured in args on recursive call) then the perf issues you mentioned don't apply. The latest version of JavaScript will include this optimization. I also disagree wrt it being more difficult to debug, understand, etc. Your mileage may vary here.
- jackfoxy 11y agoRecursion really only works in languages that support it well. In some languages recursion is simply an unnatural act.