5 ms·

Functional programming also emphasizes the use of recursion, which nearly always makes an algorithm much harder to understand.

by xyzzy4 11y ago

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 ago
  I 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 ago
      PS Another way to implement function calls (and thus recursion) is transformation into continuation passing style.
  - Gratsby 11y ago
    You 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 ago
    Correct 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 ago
      Some 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 ago
    True 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 ago
  Recursion really only works in languages that support it well. In some languages recursion is simply an unnatural act.
eru 11y ago
Why? First, loops are only a special case of recursion, and trying to shoehorn everything into that special is actually hard to read. Second, functional programming usually emphasises combinators like map, filter, reduce/foldr. Those are easier to read than either naked recursion or loops.
- coldtea 11y ago
  >Why? First, loops are only a special case of recursion In theory. In the actual world, loops are how we're used to think about doing N things.
  - eru 11y ago
    If `we' is imperatively trained programmers, then Yes. For anyone else---normal people without programming experience, or programmers trained in different paradigms---loops are not special. Of course, we mostly talk about programmers here, and imperatively trained programmers are in the majority. In any case, lots of languages have gotten map and filter, and people seem to adapt to them just fine. We just have to wait another decade for the more interesting combinators to trickle down.
    - coldtea 11y ago
      >If `we' is imperatively trained programmers, then Yes. No, we refers to both "imperatively trained programmers", and, more especially, laymen. >For anyone else---normal people without programming experience, or programmers trained in different paradigms---loops are not special I very much doubt any layman who does anything repetitive (e.g. runs 10 laps) thinks of it as recursion as opposed to keeping a mental index and thinking it similarly to a loop (without knowing the terminology of programming of course). >In any case, lots of languages have gotten map and filter, and people seem to adapt to them just fine. Those are just abstracted loops though, not recursion.
      - eru 11y ago
        I'd assume laymen think in terms of combinators, ie like map (do this operation to all the things I have), or filter (through out all the widgets that fail the test). Thinking in terms of indices is pretty painful. > Those are just abstracted loops though, not recursion. Map and filter on a tree is about as recursive as it gets. Loops are the special case of recursion that does work well on linear data structures like linked lists and arrays, yes.
nommm-nommm 11y ago
Recursion is great! I find recursive algorithms much easier to understand
T-R 11y ago
Explicit use of recursion in functional programming is widely considered to be low level and bad form, like writing all your loops with gotos in a procedural/OOP language (as was the primary argument of the Bananas, Lenses, Envelopes, and Barbed Wire paper), it's just commonly used in intro material in a "this is how you would do this by hand" fashion. For things that fall outside of that, you always have the option of monadic loops if it makes the code clearer.

Functional programming also emphasizes the use of recursion, which nearly always makes an algorithm much harder to understand.

by xyzzy4 11y ago

Functional programming also emphasizes the use of recursion, which nearly always makes an algorithm much harder to understand.

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 ago
I 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 ago
    PS Another way to implement function calls (and thus recursion) is transformation into continuation passing style.
- Gratsby 11y ago
  You 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 ago
  Correct 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 ago
    Some 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 ago
  True 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 ago
Recursion really only works in languages that support it well. In some languages recursion is simply an unnatural act.

eru 11y ago

Why? First, loops are only a special case of recursion, and trying to shoehorn everything into that special is actually hard to read. Second, functional programming usually emphasises combinators like map, filter, reduce/foldr. Those are easier to read than either naked recursion or loops.

coldtea 11y ago
>Why? First, loops are only a special case of recursion In theory. In the actual world, loops are how we're used to think about doing N things.
- eru 11y ago
  If `we' is imperatively trained programmers, then Yes. For anyone else---normal people without programming experience, or programmers trained in different paradigms---loops are not special. Of course, we mostly talk about programmers here, and imperatively trained programmers are in the majority. In any case, lots of languages have gotten map and filter, and people seem to adapt to them just fine. We just have to wait another decade for the more interesting combinators to trickle down.
  - coldtea 11y ago
    >If `we' is imperatively trained programmers, then Yes. No, we refers to both "imperatively trained programmers", and, more especially, laymen. >For anyone else---normal people without programming experience, or programmers trained in different paradigms---loops are not special I very much doubt any layman who does anything repetitive (e.g. runs 10 laps) thinks of it as recursion as opposed to keeping a mental index and thinking it similarly to a loop (without knowing the terminology of programming of course). >In any case, lots of languages have gotten map and filter, and people seem to adapt to them just fine. Those are just abstracted loops though, not recursion.
    - eru 11y ago
      I'd assume laymen think in terms of combinators, ie like map (do this operation to all the things I have), or filter (through out all the widgets that fail the test). Thinking in terms of indices is pretty painful. > Those are just abstracted loops though, not recursion. Map and filter on a tree is about as recursive as it gets. Loops are the special case of recursion that does work well on linear data structures like linked lists and arrays, yes.

nommm-nommm 11y ago

Recursion is great! I find recursive algorithms much easier to understand

T-R 11y ago

Explicit use of recursion in functional programming is widely considered to be low level and bad form, like writing all your loops with gotos in a procedural/OOP language (as was the primary argument of the Bananas, Lenses, Envelopes, and Barbed Wire paper), it's just commonly used in intro material in a "this is how you would do this by hand" fashion. For things that fall outside of that, you always have the option of monadic loops if it makes the code clearer.