19 ms·

I don’t understand this book. It begins by explaining how great recursion is. Then later it explains why you shouldn’t use it for large inputs in the two chos

I don’t understand this book. It begins by explaining how great recursion is. Then later it explains why you shouldn’t use it for large inputs in the two chosen languages (JavaScript and Python) to avoid blowing up the stack. Then it argues that tail call optimisation is bad! So when is a good time to use recursion?!? And what is the purpose of the book?

mrkeen 2y ago
> Then it argues that tail call optimisation is bad! I didn't think I'd find this, so I went digging. Sure enough: The disadvantage of tail recursion is that it requires rearranging your recursive function so that the last action is returning the recursive call’s return value. This can make our recursive code even more unreadable. Tail recursive functions require rearranging their code to make them suitable for the tail call optimization feature of the compiler or interpreter. Personally, I take the stance that the tail recursion technique should never be used. What can one do, but just disagree I guess? > And what is the purpose of the book? To straw-man functional programming with a one-two punch of "I already have that" and "it's bad" so devs never leave Python/JS land to find this stuff out for themselves ;)
- tpoacher 2y ago
  Yep. Especially when a tail recursion can be immediately converted to an equivalent loop by definition (and vice versa). A bizzare comment at best, from someone writing a book on recursion.
dahart 2y ago
Recursion is great for CS education, but recursion should be rarely/never used in production code. Tail call recursion is one exception to that - I see it in production code occasionally. But tail call recursion is limited to cases of 1-dimensional recursion that can be transformed into iteration - and iteration is better anyway, so even tail calls need some extra justification for use in production code. Check out the famous NASA coding rules. Rule number one is no recursion. :P https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Developing_Safety-Critical_Code https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev... When I was a game programmer, recursion was to be avoided at all costs. Even as a past graphics researcher, I’ve used recursive flood-fill as part of several research papers, and recursive flood-fill on a large image will blow your stack, so I always translate it into a heap allocation and implement recursion using an iterative algorithm with breadcrumbs for backtracking. It’s common for there to be a way to increase the stack size, but it’s just really annoying and sometimes not possible to always be able to do that on any machine you want to run on. One case where recursion or something that looks like recursion is used in production code is when dealing with tree data structures. Those are common, and traversing them is common. Recursion is acceptable for that - though people who care about performance will still optimize it into an iterative algorithm whenever possible (which is most of the time).
- YeGoblynQueenne 2y ago
  >> Recursion is great for CS education, but recursion should be rarely/never used in production code. How so? Do you mean "in Python" or similar languages, or do you mean in general? I write all my code in Prolog basically and there it's all recursion, no iteration. There's no iteration constructs. The Prolog interpreter has tail-call optimisation and you learn to use it soon enough. Anyway let's not be all dogmatic like that. Rules always have exceptions (including this one ha ha) so there's no point in being so absolute about things. >> Check out the famous NASA coding rules. Rule number one is no recursion. :P https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev... Edit: Rule no 1 from NASA is "avoid complex control flow". From your link: 1. Avoid complex flow constructs, such as goto and recursion. Seems that even NASA accepts a modicum of GOTOs and recursion.
  - dahart 2y ago
    Correct NASA’s first rule isn’t absolute, it says “avoid”, but they do have a hard rule that loop (recursion) bounds must have fixed bounds, which still rules out most non-trivial recursion. > How so? Stack + function call recursion is almost always slower and more memory intensive than alternatives, not to mention risk of stack overflow, so most people who care about perf and mem will opt out anyway. Tail recursion isn’t included, because it optimizes out the function call, and tail recursion is iteration anyway. If tail recursion isn’t an option, it means a tree or multi-branch recursion, which is generally speaking difficult to reason about and difficult to bound, so error prone. People who care about safety, like NASA, avoid recursion for those reasons. I’m sure they will use recursion when it’s the only choice, or the best choice. Choice of data structure might affect whether recursion is best. > I write all my code in Prolog Interesting! For what industry? I‘ll admit I’ve never met any production Prolog, but of course the recursion rule doesn’t apply to a language that has no other choice. Wikipedia kinda bluntly suggests that Prolog is best for research and education, and rarely used in production code…?
    - YeGoblynQueenne 2y ago
      What is "non-trivial" recursion? Honest question, I'm not familiar with the term. E.g. is reversing a list recursively "non-trivial"? I think the 2nd rule ("All loops must have fixed bounds. This prevents runaway code.") refers to numerical bounds, so if you take it literally it would also eliminate e.g. while loops with a boolean condition, but I don't know if that's the intention. In NASA, with very expensive equipment on the line, maybe; but for most other environments that would be an onerous requirement. In any case you can turn any recursion with non-numeric bounds to one with numeric bounds easily. You do that by adding a parameter that counts the recursion steps and exits if the count exceeds a limit. For added security, you can do this check in each "clause" (literal or figurative) of the recursive procedure, not just the boundary condition. Then you have depth-limited recursion and bobs your ankle. Or Bob is your uncle, I'm never sure about that one. >> Interesting! For what industry? I‘ll admit I’ve never met any production Prolog, but of course the recursion rule doesn’t apply to a language that has no other choice. Wikipedia kinda bluntly suggests that Prolog is best for research and education, and rarely used in production code…? Most of my Prolog coding has been for my PhD and post-doc research of course but I'm now in my third industry contract where I work almost exclusively with Prolog (the rest is a bit of shell scripting and the like). I don't want to say what the industry is, or the job, but as a for instance my two previous Prolog industry gigs were in an AI startup and the other working on a legacy system for management of rental car fleets, both in France two years ago. The car system was written in the '90s and it had changed many hands since then so it was a royal mess and I didn't stay long working on it but I recently spoke with one of the other devs and it's still going. There's plenty of that legacy Prolog expert system code around, all left over from the '90s, written before the winter. Sicstus, the biggest commercial Prolog vendor, used to brag on their landing page that if you've booked any air travel recently then chances are you used a Prolog-based system, which shouldn't come as a surprise. After all, every time you use online banking, you are using a system based on COBOL and running on a mainframe. That claim has recently disappeared from the Sicstus site though and I don't know what that means. Anyway Prolog coders occasionally hear about gigs working on stuff like that through the grapevine, but judging from my experience those are mainly maintained by programmers who have never seen Prolog before in their lives, until they're thrown in at the deep end an have to make do. But I see you're making a distinction between "research and education" and "production code"? Why's that? The code I write for my research is production code. I can tell you that with a straight face because I've worked in the industry many years before I did my PhD and my Prolog code is much more stable, and maintainable to boot, than 90% of the rickety, held together with bits of string and gaffer tape, "production" code I worked with as an industry code monkey. And btw I'm still a code monkey. That's what makes code "production": who writes it, not who it is for. Btw my post-doc Prolog code had to run on a robot that cost a few thousand quid (I'm in the UK) so it had to be industrial strength. I never got to test it because my funding er expired. In academia, you have to be careful who you're telling hard, technical truths to. So now I'm working in the industry.

mrkeen 2y ago

> Then it argues that tail call optimisation is bad! I didn't think I'd find this, so I went digging. Sure enough: The disadvantage of tail recursion is that it requires rearranging your recursive function so that the last action is returning the recursive call’s return value. This can make our recursive code even more unreadable. Tail recursive functions require rearranging their code to make them suitable for the tail call optimization feature of the compiler or interpreter. Personally, I take the stance that the tail recursion technique should never be used. What can one do, but just disagree I guess? > And what is the purpose of the book? To straw-man functional programming with a one-two punch of "I already have that" and "it's bad" so devs never leave Python/JS land to find this stuff out for themselves ;)

tpoacher 2y ago
Yep. Especially when a tail recursion can be immediately converted to an equivalent loop by definition (and vice versa). A bizzare comment at best, from someone writing a book on recursion.

dahart 2y ago

Recursion is great for CS education, but recursion should be rarely/never used in production code. Tail call recursion is one exception to that - I see it in production code occasionally. But tail call recursion is limited to cases of 1-dimensional recursion that can be transformed into iteration - and iteration is better anyway, so even tail calls need some extra justification for use in production code. Check out the famous NASA coding rules. Rule number one is no recursion. :P https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Developing_Safety-Critical_Code https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev... When I was a game programmer, recursion was to be avoided at all costs. Even as a past graphics researcher, I’ve used recursive flood-fill as part of several research papers, and recursive flood-fill on a large image will blow your stack, so I always translate it into a heap allocation and implement recursion using an iterative algorithm with breadcrumbs for backtracking. It’s common for there to be a way to increase the stack size, but it’s just really annoying and sometimes not possible to always be able to do that on any machine you want to run on. One case where recursion or something that looks like recursion is used in production code is when dealing with tree data structures. Those are common, and traversing them is common. Recursion is acceptable for that - though people who care about performance will still optimize it into an iterative algorithm whenever possible (which is most of the time).

YeGoblynQueenne 2y ago
>> Recursion is great for CS education, but recursion should be rarely/never used in production code. How so? Do you mean "in Python" or similar languages, or do you mean in general? I write all my code in Prolog basically and there it's all recursion, no iteration. There's no iteration constructs. The Prolog interpreter has tail-call optimisation and you learn to use it soon enough. Anyway let's not be all dogmatic like that. Rules always have exceptions (including this one ha ha) so there's no point in being so absolute about things. >> Check out the famous NASA coding rules. Rule number one is no recursion. :P https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev https://en.wikipedia.org/wiki/The_Power_of_10:_Rules_for_Dev... Edit: Rule no 1 from NASA is "avoid complex control flow". From your link: 1. Avoid complex flow constructs, such as goto and recursion. Seems that even NASA accepts a modicum of GOTOs and recursion.
- dahart 2y ago
  Correct NASA’s first rule isn’t absolute, it says “avoid”, but they do have a hard rule that loop (recursion) bounds must have fixed bounds, which still rules out most non-trivial recursion. > How so? Stack + function call recursion is almost always slower and more memory intensive than alternatives, not to mention risk of stack overflow, so most people who care about perf and mem will opt out anyway. Tail recursion isn’t included, because it optimizes out the function call, and tail recursion is iteration anyway. If tail recursion isn’t an option, it means a tree or multi-branch recursion, which is generally speaking difficult to reason about and difficult to bound, so error prone. People who care about safety, like NASA, avoid recursion for those reasons. I’m sure they will use recursion when it’s the only choice, or the best choice. Choice of data structure might affect whether recursion is best. > I write all my code in Prolog Interesting! For what industry? I‘ll admit I’ve never met any production Prolog, but of course the recursion rule doesn’t apply to a language that has no other choice. Wikipedia kinda bluntly suggests that Prolog is best for research and education, and rarely used in production code…?
  - YeGoblynQueenne 2y ago
    What is "non-trivial" recursion? Honest question, I'm not familiar with the term. E.g. is reversing a list recursively "non-trivial"? I think the 2nd rule ("All loops must have fixed bounds. This prevents runaway code.") refers to numerical bounds, so if you take it literally it would also eliminate e.g. while loops with a boolean condition, but I don't know if that's the intention. In NASA, with very expensive equipment on the line, maybe; but for most other environments that would be an onerous requirement. In any case you can turn any recursion with non-numeric bounds to one with numeric bounds easily. You do that by adding a parameter that counts the recursion steps and exits if the count exceeds a limit. For added security, you can do this check in each "clause" (literal or figurative) of the recursive procedure, not just the boundary condition. Then you have depth-limited recursion and bobs your ankle. Or Bob is your uncle, I'm never sure about that one. >> Interesting! For what industry? I‘ll admit I’ve never met any production Prolog, but of course the recursion rule doesn’t apply to a language that has no other choice. Wikipedia kinda bluntly suggests that Prolog is best for research and education, and rarely used in production code…? Most of my Prolog coding has been for my PhD and post-doc research of course but I'm now in my third industry contract where I work almost exclusively with Prolog (the rest is a bit of shell scripting and the like). I don't want to say what the industry is, or the job, but as a for instance my two previous Prolog industry gigs were in an AI startup and the other working on a legacy system for management of rental car fleets, both in France two years ago. The car system was written in the '90s and it had changed many hands since then so it was a royal mess and I didn't stay long working on it but I recently spoke with one of the other devs and it's still going. There's plenty of that legacy Prolog expert system code around, all left over from the '90s, written before the winter. Sicstus, the biggest commercial Prolog vendor, used to brag on their landing page that if you've booked any air travel recently then chances are you used a Prolog-based system, which shouldn't come as a surprise. After all, every time you use online banking, you are using a system based on COBOL and running on a mainframe. That claim has recently disappeared from the Sicstus site though and I don't know what that means. Anyway Prolog coders occasionally hear about gigs working on stuff like that through the grapevine, but judging from my experience those are mainly maintained by programmers who have never seen Prolog before in their lives, until they're thrown in at the deep end an have to make do. But I see you're making a distinction between "research and education" and "production code"? Why's that? The code I write for my research is production code. I can tell you that with a straight face because I've worked in the industry many years before I did my PhD and my Prolog code is much more stable, and maintainable to boot, than 90% of the rickety, held together with bits of string and gaffer tape, "production" code I worked with as an industry code monkey. And btw I'm still a code monkey. That's what makes code "production": who writes it, not who it is for. Btw my post-doc Prolog code had to run on a robot that cost a few thousand quid (I'm in the UK) so it had to be industrial strength. I never got to test it because my funding er expired. In academia, you have to be careful who you're telling hard, technical truths to. So now I'm working in the industry.