6 ms·

I was thinking about this the other day too. Recursion in CS101 is taught in such a bizarre way. At least it was back when I was in CS101. It was almost as thou

by nbevans 11y ago

I was thinking about this the other day too. Recursion in CS101 is taught in such a bizarre way. At least it was back when I was in CS101. It was almost as though CS tries to discourage its usage simply because "most minds cannot understand it as easily as iterative loops".

fleitz 11y ago
I prefer it to loops, I find it more concise, it makes you really think about what your code is doing when you make it recursive. Often I find subtle bugs in my loops where as with recursion the compiler seems to pick them up for me.
- bliti 11y ago
  In what scenario do you prefer recursion over a loop? Your comment made me think of code readability and maintainability. But I'm not judging. Really curious how you manage to prefer recursion over loops.
  - mda 11y ago
    If working with trees, recursion is usually easier to understand.
    - jalanb 11y ago
      If working with recursively expressed data, recursively expressed algorithms are usually easier to understand.
  - StefanHamminga 11y ago
    My 2c: Building a hierarchical structure requiring opening and closing tags/code/etc (like HTML) is where I like to use recursion. The code structure matches the data structure, so you only have to reason about it once.
  - whatever12981 11y ago
    Anecdote: After 12 hours of programming, I still had to implement some easy string search. I could not think straight at that stage and several imperative solutions failed. Then I thought "dammit, let's use a functional approach with recursion". It was faster to write, tail recursive, and correct the first time.
    - eterm 11y ago
      Which environment are you working in that doesn't have a string search as part of the standard library?
      - whatever72163 11y ago
        INTERCAL. Seriously, what does it have to do with the point I made?
  - gjm11 11y ago
    Other commenters have already mentioned that recursion is often a more natural fit for "recursively-defined" structures like trees. Here's an example using nothing more exotic than integers. Suppose you want to compute the greatest common divisor of two non-negative integers. There's a famous algorithm that goes all the way back to Euclid's Elements, which you can write iteratively like this: def gcd(a,b): if a<b: a,b = b,a while b != 0: a,b = b,a%b return a That's pretty nice, and it's the way I would usually implement it. But in terms of readability I think the following is better: def gcd(a,b): if a<b: return gcd(b,a) if b==0: return a return gcd(b, a%b) because it makes it explicit that the point is that at every point in the computation you're replacing gcd(a,b) with gcd(a',b') in such a way that the calculation keeps getting easier. It turns out that if the gcd of a,b is d then there are always integers x,y such that ax+by=d, and it's sometimes useful to compute x,y along with d. (For instance: if d=1 then you have ax=1 mod b, so this gives you an efficient way of computing reciprocals in modular arithmetic.) Here's how that goes, iteratively and then recursively. (I notice that I've used two extra state variables for the iterative version. That's what seems like the most natural approach. I'm not sure whether there's a convenient way to use only two.) def xgcd(a,b): p,q,r,s = 1,0,0,1 # a = p.a0+q.b0, b = r.a0+s.b0 if a<b: a,b, p,q, r,s = b,a, r,s, p,q while b != 0: k = a//b a,b, p,q, r,s = b,a-k*b, r,s, p-k*r,q-k*s return a,p,q def xgcd(a,b): if a<b: d,x,y = xgcd(b,a) return d,y,x if b==0: return a,1,0 k = a//b d,x,y = xgcd(b,a-k*b) # d = x.b + y.(a-kb) return d,y,x-k*y The difference isn't dramatic in any of these cases, but I think the recursive versions are clearer because the code is closer to the underlying mathematical theorems -- e.g., gcd(a,b) = gcd(b, a mod b) -- that make it work. [EDITED to add:] Perhaps it's useful to think of it this way. If you wanted to explain how, say, that iterative xgcd function works, you'd do it with a loop invariant; in fact, I actually wrote one, in that first comment "explaining" what p,q,r,s signify. (In real code I would be more verbose about it.) The recursive function gets the same idea across in the language itself: each iteration of the loop becomes a call to xgcd, and the loop invariant becomes the fact that the corresponding call to xgcd actually computes what it's supposed to compute.
    - mbucc 11y ago
  - chriswarbo 11y ago
    I prefer recursion to loops since loops bundle everything together in one environment; variables left over from previous iterations are still in scope, which is confusing and may cause problems, e.g. using a variable before it's been updated for this iteration, or after it's been updated for the next iteration, etc. Recursion is just function calls. The only things which are in scope are those required by this iteration, accepted as arguments. The only thing I need to produce is a return value. This is a small, well-defined interface, as opposed to the self-interfering spaghetti code of a loop. By accepting values as arguments and calling functions with different values, the problem of when and what to assign variables goes away; the language does it automatically by binding arguments. Also, recursion (like function calls in general) allows thinking in terms of values, which are timeless and explicit in the code, rather than state, which is implicit and varies during execution. Semi-related: http://chriswarbo.net/blog/2012-10-02-looping_in_javascript.html http://chriswarbo.net/blog/2012-10-02-looping_in_javascript....
  - tel 11y ago
    I think it's rather universal that, for instance, a depth-first tree traversal is best done recursively. In my experience, I almost always prefer recursion since it allows me to work more closely with the structure of the original data that I'm interested in instead of a set of a proxy indices which I have to track separately.
- deleted 11y ago
  [deleted]
mixedCase 11y ago
>It was almost as though CS tries to discourage its usage simply because "most minds cannot understand it as easily as iterative loops". Wouldn't that be enough reason? They're supposed to teach you how to write good code, and that includes readable code.
- derefr 11y ago
  No, "they" are not. Maybe you're thinking of Software Engineering? Computer Science is supposed to teach you about the branch of mathematics called Computer Science. Recursion is a very important part of that—important enough that the need to address it early was one of the things that made Scheme an obvious choice for a teaching language for decades.
  - argonaut 11y ago
    No. This is an overly restrictive definition. Computer Science is it's own, highly diverse field, composed of software engineering, algorithms, theory of computation, human-computer-interaction, AI, systems engineering, databases, security, graphics, scientific computing, and many other sub-divisions. CS hasn't been solely a branch of mathematics for decades. See what Stanford considers part of CS: http://www-cs.stanford.edu/research http://www-cs.stanford.edu/research See what Berkeley considers part of EECS: http://www.eecs.berkeley.edu/Research/Areas/ http://www.eecs.berkeley.edu/Research/Areas/
  - pjmlp 11y ago
    In Portuguese universities informatics Software Engineering and Computer Science are part of the same degree, there isn't a clear distinction as such. It is up to you to choose which lectures you want to use your optional credits for.
    - the_af 11y ago
      True, there often is no clear distinction. On the other hand, I studied CS in South America, and I can count on one hand the lectures which aimed to teach you "how to write good code". Maybe one or two of them, and only in the macro "good software engineering practices" sense. Most of the others assumed you sort of picked up how to code on your own, or that you asked other students or TAs on the side. There absolutely were NO "how to code" lectures, and the overall idea you got was that CS was a theory-heavy degree. Recursion, proofs, type theory, graph theory, etc, were absolutely the focus of the degree. There was a different degree called "Software Engineering" (and not CS) from the same university, but I think they heavily overlap in content, so in practice the point remains.
rer0tsaz 11y ago
Iterative loops are much easier to analyze and reason about, by humans and by computers. For example, they always terminate. To paraphrase Dijkstra, "I regard general recursion as an order of magnitude more complicated than just repetition, and I don't like to crack an egg with a sledgehammer." https://tinyletter.com/programmingphilosophy/letters/i-don-t-like-to-crack-an-egg-with-a-sledgehammer https://tinyletter.com/programmingphilosophy/letters/i-don-t...
- pjmlp 11y ago
  > For example, they always terminate. How do you terminate? for(;;) { }
  - meggar 11y ago
    break;
    - pjmlp 11y ago
      Not all programming languages have break; C syntax was just an example. Also break is no different from using return (to keep C syntax as example) when recursing. If you guard break with if then you also need to prove if the "if" condition does indeed provide a dataflow path to break.
      - AnimalMuppet 11y ago
        > If you guard break with if then you also need to prove if the "if" condition does indeed provide a dataflow path to break. In all cases, for all possible inputs. On the other hand, if that's what your for loop looks like, you probably have the same problem of proving that your recursion terminates (in all cases, for all possible inputs).
        pjmlp 11y ago
        Of course, I was just arguing against the OP that all loops terminate.
pjmlp 11y ago
I never got what the problem with recursion in CS101 might be. In Portuguese universities, by time you get to this programming issues you already had enough maths to be able to relate recursion to how mathematical proofs work. At least it was so for me and most of my friends back in the 90's.

by nbevans 11y ago

fleitz 11y ago

I prefer it to loops, I find it more concise, it makes you really think about what your code is doing when you make it recursive. Often I find subtle bugs in my loops where as with recursion the compiler seems to pick them up for me.

bliti 11y ago
In what scenario do you prefer recursion over a loop? Your comment made me think of code readability and maintainability. But I'm not judging. Really curious how you manage to prefer recursion over loops.
- mda 11y ago
  If working with trees, recursion is usually easier to understand.
  - jalanb 11y ago
    If working with recursively expressed data, recursively expressed algorithms are usually easier to understand.
- StefanHamminga 11y ago
  My 2c: Building a hierarchical structure requiring opening and closing tags/code/etc (like HTML) is where I like to use recursion. The code structure matches the data structure, so you only have to reason about it once.
- whatever12981 11y ago
  Anecdote: After 12 hours of programming, I still had to implement some easy string search. I could not think straight at that stage and several imperative solutions failed. Then I thought "dammit, let's use a functional approach with recursion". It was faster to write, tail recursive, and correct the first time.
  - eterm 11y ago
    Which environment are you working in that doesn't have a string search as part of the standard library?
    - whatever72163 11y ago
      INTERCAL. Seriously, what does it have to do with the point I made?
- gjm11 11y ago
  Other commenters have already mentioned that recursion is often a more natural fit for "recursively-defined" structures like trees. Here's an example using nothing more exotic than integers. Suppose you want to compute the greatest common divisor of two non-negative integers. There's a famous algorithm that goes all the way back to Euclid's Elements, which you can write iteratively like this: def gcd(a,b): if a<b: a,b = b,a while b != 0: a,b = b,a%b return a That's pretty nice, and it's the way I would usually implement it. But in terms of readability I think the following is better: def gcd(a,b): if a<b: return gcd(b,a) if b==0: return a return gcd(b, a%b) because it makes it explicit that the point is that at every point in the computation you're replacing gcd(a,b) with gcd(a',b') in such a way that the calculation keeps getting easier. It turns out that if the gcd of a,b is d then there are always integers x,y such that ax+by=d, and it's sometimes useful to compute x,y along with d. (For instance: if d=1 then you have ax=1 mod b, so this gives you an efficient way of computing reciprocals in modular arithmetic.) Here's how that goes, iteratively and then recursively. (I notice that I've used two extra state variables for the iterative version. That's what seems like the most natural approach. I'm not sure whether there's a convenient way to use only two.) def xgcd(a,b): p,q,r,s = 1,0,0,1 # a = p.a0+q.b0, b = r.a0+s.b0 if a<b: a,b, p,q, r,s = b,a, r,s, p,q while b != 0: k = a//b a,b, p,q, r,s = b,a-k*b, r,s, p-k*r,q-k*s return a,p,q def xgcd(a,b): if a<b: d,x,y = xgcd(b,a) return d,y,x if b==0: return a,1,0 k = a//b d,x,y = xgcd(b,a-k*b) # d = x.b + y.(a-kb) return d,y,x-k*y The difference isn't dramatic in any of these cases, but I think the recursive versions are clearer because the code is closer to the underlying mathematical theorems -- e.g., gcd(a,b) = gcd(b, a mod b) -- that make it work. [EDITED to add:] Perhaps it's useful to think of it this way. If you wanted to explain how, say, that iterative xgcd function works, you'd do it with a loop invariant; in fact, I actually wrote one, in that first comment "explaining" what p,q,r,s signify. (In real code I would be more verbose about it.) The recursive function gets the same idea across in the language itself: each iteration of the loop becomes a call to xgcd, and the loop invariant becomes the fact that the corresponding call to xgcd actually computes what it's supposed to compute.
  - mbucc 11y ago
- chriswarbo 11y ago
  I prefer recursion to loops since loops bundle everything together in one environment; variables left over from previous iterations are still in scope, which is confusing and may cause problems, e.g. using a variable before it's been updated for this iteration, or after it's been updated for the next iteration, etc. Recursion is just function calls. The only things which are in scope are those required by this iteration, accepted as arguments. The only thing I need to produce is a return value. This is a small, well-defined interface, as opposed to the self-interfering spaghetti code of a loop. By accepting values as arguments and calling functions with different values, the problem of when and what to assign variables goes away; the language does it automatically by binding arguments. Also, recursion (like function calls in general) allows thinking in terms of values, which are timeless and explicit in the code, rather than state, which is implicit and varies during execution. Semi-related: http://chriswarbo.net/blog/2012-10-02-looping_in_javascript.html http://chriswarbo.net/blog/2012-10-02-looping_in_javascript....
- tel 11y ago
  I think it's rather universal that, for instance, a depth-first tree traversal is best done recursively. In my experience, I almost always prefer recursion since it allows me to work more closely with the structure of the original data that I'm interested in instead of a set of a proxy indices which I have to track separately.
deleted 11y ago
[deleted]

mixedCase 11y ago

>It was almost as though CS tries to discourage its usage simply because "most minds cannot understand it as easily as iterative loops". Wouldn't that be enough reason? They're supposed to teach you how to write good code, and that includes readable code.

derefr 11y ago
No, "they" are not. Maybe you're thinking of Software Engineering? Computer Science is supposed to teach you about the branch of mathematics called Computer Science. Recursion is a very important part of that—important enough that the need to address it early was one of the things that made Scheme an obvious choice for a teaching language for decades.
- argonaut 11y ago
  No. This is an overly restrictive definition. Computer Science is it's own, highly diverse field, composed of software engineering, algorithms, theory of computation, human-computer-interaction, AI, systems engineering, databases, security, graphics, scientific computing, and many other sub-divisions. CS hasn't been solely a branch of mathematics for decades. See what Stanford considers part of CS: http://www-cs.stanford.edu/research http://www-cs.stanford.edu/research See what Berkeley considers part of EECS: http://www.eecs.berkeley.edu/Research/Areas/ http://www.eecs.berkeley.edu/Research/Areas/
- pjmlp 11y ago
  In Portuguese universities informatics Software Engineering and Computer Science are part of the same degree, there isn't a clear distinction as such. It is up to you to choose which lectures you want to use your optional credits for.
  - the_af 11y ago
    True, there often is no clear distinction. On the other hand, I studied CS in South America, and I can count on one hand the lectures which aimed to teach you "how to write good code". Maybe one or two of them, and only in the macro "good software engineering practices" sense. Most of the others assumed you sort of picked up how to code on your own, or that you asked other students or TAs on the side. There absolutely were NO "how to code" lectures, and the overall idea you got was that CS was a theory-heavy degree. Recursion, proofs, type theory, graph theory, etc, were absolutely the focus of the degree. There was a different degree called "Software Engineering" (and not CS) from the same university, but I think they heavily overlap in content, so in practice the point remains.

rer0tsaz 11y ago

Iterative loops are much easier to analyze and reason about, by humans and by computers. For example, they always terminate. To paraphrase Dijkstra, "I regard general recursion as an order of magnitude more complicated than just repetition, and I don't like to crack an egg with a sledgehammer." https://tinyletter.com/programmingphilosophy/letters/i-don-t-like-to-crack-an-egg-with-a-sledgehammer https://tinyletter.com/programmingphilosophy/letters/i-don-t...

pjmlp 11y ago
> For example, they always terminate. How do you terminate? for(;;) { }
- meggar 11y ago
  break;
  - pjmlp 11y ago
    Not all programming languages have break; C syntax was just an example. Also break is no different from using return (to keep C syntax as example) when recursing. If you guard break with if then you also need to prove if the "if" condition does indeed provide a dataflow path to break.
    - AnimalMuppet 11y ago
      > If you guard break with if then you also need to prove if the "if" condition does indeed provide a dataflow path to break. In all cases, for all possible inputs. On the other hand, if that's what your for loop looks like, you probably have the same problem of proving that your recursion terminates (in all cases, for all possible inputs).
      - pjmlp 11y ago
        Of course, I was just arguing against the OP that all loops terminate.

pjmlp 11y ago

I never got what the problem with recursion in CS101 might be. In Portuguese universities, by time you get to this programming issues you already had enough maths to be able to relate recursion to how mathematical proofs work. At least it was so for me and most of my friends back in the 90's.