14 ms·

Recursive Python Considered Harmful

15 points by clockwork_189 15y ago

vph 15y ago
>Given that any recursive function can be written using a while loop with O(1) memory bounds, recursion seems quite a poor choice for all practical purposes. It is very unfortunate that many programmers (including Guildo, circa 2009) think this way. Guildo in particular, when he talked about recursion, his state of mind is about "cons" and "tail" of Scheme. On the other hand, it is undeniable that algorithmic thinking and problem solving skills are critical to being a good programmer. And as of today those who are trained in the tradition of the Computer Science discipline are equipped with an array of algorithmic strategies all based on recursion. Techniques such as divide and conquer, dynamic programming and much more are all based on the idea of solving a problem in terms of itself, i.e. recursion. When a programming language eschew recursive strategies, it inadvertently wastes precious skills that are taught to programmers. Recursions are hard, but they are very powerful, when used properly. There are many problems that can be solved easily and faster with recursion, and you can't simply convert them to loops.
- baddox 15y ago
  Based on a recent talk I attended, I believe that Guido admits that it's purely a matter of opinion, but he always has to "unroll" the recursive in his head to be able to figure out what recursive code does, so he concludes that it might as well be written the way that he thinks. I agree with that last part, but I can't imagine thinking of every algorithm iteratively. Binary search, merge sort, and pretty much any tree algorithm are examples of algorithms that (to me) are much less natural to thing of iteratively.
rheide 15y ago
Not implementing proper tail recursion in Python considered harmful.
prodigal_erik 15y ago
> recursion, despite it cleanliness, improves readability at a significant cost in memory Tradeoffs like that are what highly dynamic languages are all about. You shouldn't be using Python (yet) if the natural expression of your algorithm is too expensive for your problem size (with today's implementations). Making your Python non-idiomatic and hard to read will cost you its advantages, and won't even buy you much time before you find yourself porting to Java or something similarly optimized.
- baddox 15y ago
  What you say is true, but you seem to be implying that only recursive algorithms are idiomatic in Python. I would disagree: pretty much anything you do on sequential data in Python is done idiomatically with a for loop or a comprehension, neither of which are particularly recursive.
  - DougBTX 15y ago
    > you seem to be implying that only recursive algorithms are idiomatic in Python. He didn't say that, so thankfully there's nothing to disagree with.
    - baddox 15y ago
      Re-read what he said. It's a pretty clear implication that recursive code is idiomatic in Python.
      - prodigal_erik 15y ago
        Some algorithms solve a problem by examining solutions to other instances of the same problem. Minimax and quicksort work this way, as do a lot of tree and graph traversal problems. Implementations of these algorithms are inherently recursive, in the sense that you're going to need to say "carry out the whole algorithm again here". You can always fake recursion by creating objects to hold the state of the call graph (or stack, if you don't have continuations), but that's so cumbersome to write or read that you'll quickly be better off in a language that doesn't force you to do it, just as we've now all adopted languages which actually provide functions rather than faking it by saving and restoring variables around GOTOs (I wish I were kidding).
tzs 15y ago
Warning for iPad users: OnSwipe.
CrLf 15y ago
I think it is agreed that recursion is the best approach in many cases. Many problems have a simple recursive solution, but become very complicated if solved by iteration. But I'm under the impression that this is seldom (if ever) the case with recursive solutions that can benefit from tail call elimination... In this case, an iterative solution is just as simple (or complicated). It is a matter of taste. When this is not the case, you can't perform this optimization anyway. Am I wrong here?
cousin_it 15y ago
> Given that any recursive function can be written using a while loop with O(1) memory bounds I think that's only true if the function makes only one recursive call, like computing the Fibonacci numbers. If the function calls itself recursively twice, it may end up using a lot of memory, e.g. the Ackermann function.

15 points by clockwork_189 15y ago

vph 15y ago

>Given that any recursive function can be written using a while loop with O(1) memory bounds, recursion seems quite a poor choice for all practical purposes. It is very unfortunate that many programmers (including Guildo, circa 2009) think this way. Guildo in particular, when he talked about recursion, his state of mind is about "cons" and "tail" of Scheme. On the other hand, it is undeniable that algorithmic thinking and problem solving skills are critical to being a good programmer. And as of today those who are trained in the tradition of the Computer Science discipline are equipped with an array of algorithmic strategies all based on recursion. Techniques such as divide and conquer, dynamic programming and much more are all based on the idea of solving a problem in terms of itself, i.e. recursion. When a programming language eschew recursive strategies, it inadvertently wastes precious skills that are taught to programmers. Recursions are hard, but they are very powerful, when used properly. There are many problems that can be solved easily and faster with recursion, and you can't simply convert them to loops.

baddox 15y ago
Based on a recent talk I attended, I believe that Guido admits that it's purely a matter of opinion, but he always has to "unroll" the recursive in his head to be able to figure out what recursive code does, so he concludes that it might as well be written the way that he thinks. I agree with that last part, but I can't imagine thinking of every algorithm iteratively. Binary search, merge sort, and pretty much any tree algorithm are examples of algorithms that (to me) are much less natural to thing of iteratively.

rheide 15y ago

Not implementing proper tail recursion in Python considered harmful.

prodigal_erik 15y ago

> recursion, despite it cleanliness, improves readability at a significant cost in memory Tradeoffs like that are what highly dynamic languages are all about. You shouldn't be using Python (yet) if the natural expression of your algorithm is too expensive for your problem size (with today's implementations). Making your Python non-idiomatic and hard to read will cost you its advantages, and won't even buy you much time before you find yourself porting to Java or something similarly optimized.

baddox 15y ago
What you say is true, but you seem to be implying that only recursive algorithms are idiomatic in Python. I would disagree: pretty much anything you do on sequential data in Python is done idiomatically with a for loop or a comprehension, neither of which are particularly recursive.
- DougBTX 15y ago
  > you seem to be implying that only recursive algorithms are idiomatic in Python. He didn't say that, so thankfully there's nothing to disagree with.
  - baddox 15y ago
    Re-read what he said. It's a pretty clear implication that recursive code is idiomatic in Python.
    - prodigal_erik 15y ago
      Some algorithms solve a problem by examining solutions to other instances of the same problem. Minimax and quicksort work this way, as do a lot of tree and graph traversal problems. Implementations of these algorithms are inherently recursive, in the sense that you're going to need to say "carry out the whole algorithm again here". You can always fake recursion by creating objects to hold the state of the call graph (or stack, if you don't have continuations), but that's so cumbersome to write or read that you'll quickly be better off in a language that doesn't force you to do it, just as we've now all adopted languages which actually provide functions rather than faking it by saving and restoring variables around GOTOs (I wish I were kidding).

tzs 15y ago

Warning for iPad users: OnSwipe.

CrLf 15y ago

I think it is agreed that recursion is the best approach in many cases. Many problems have a simple recursive solution, but become very complicated if solved by iteration. But I'm under the impression that this is seldom (if ever) the case with recursive solutions that can benefit from tail call elimination... In this case, an iterative solution is just as simple (or complicated). It is a matter of taste. When this is not the case, you can't perform this optimization anyway. Am I wrong here?

cousin_it 15y ago

> Given that any recursive function can be written using a while loop with O(1) memory bounds I think that's only true if the function makes only one recursive call, like computing the Fibonacci numbers. If the function calls itself recursively twice, it may end up using a lot of memory, e.g. the Ackermann function.