5 ms·

When I was writing Ansi Common Lisp I spent a while thinking about why students find recursion a difficult concept. I decided it was because they think of a fu

by pg 16y ago

When I was writing Ansi Common Lisp I spent a while thinking about why students find recursion a difficult concept. I decided it was because they think of a function as a machine for doing something. E.g. the length function as a machine that finds the lengths of lists. If you think of a function instead as a definition-- e.g. as the definition of length-- then suddenly it's not difficult anymore. At least, that was the transition I had made myself. My initial difficulty in understanding recursion was probably exacerbated by the fact that the professors themselves (at Cornell in the 1980s) had a mental model of computing that was very close to the machine, and thought the way to understand recursion was to visualize the state of the stack over time as a recursive function computed it result.

leif 16y ago
Why, though, do they think of a function as a machine for doing something? Because we tell them so. Before starting any standard CS curriculum (ignoring, for a moment, self-taught hackers), the only place a student should have heard about "functions" is in math class---where they are definitions. They get to intro Java and we tell them "no, no, that's not a function, this is a function, look, it's got variables and for loops and increments and a bunch of returns all through it, this is the real stuff, remember it!" We un-teach them about recursion, and later, when we try to re-teach it to them, we have to undo all of our previous work. In the past, there was considerable merit to un-learning the inefficient definition-style functions and learning to think closer to the machine. Today, I think there's a lot more to be gained by sticking with the math-style function-as-a-definition, because we have efficient abstractions to deal with it, but of course, this is one of the friendliest forums for that sort of philosophy. FWIW, I propose that all of academia make a distinction between pure, recursive, definition-style "functions", and imperative, stateful "methods". Probably won't catch on :-/
- eru 16y ago
  Your "methods" have also been called "procedures".
  - leif 16y ago
    sure. pick one and make people use it
silentbicycle 16y ago
Yes, recursion is tied up with baggage about stack allocation. If recursion is approached as inductive reasoning, those objections never occur. This particularly applies to tail-call optimizations and continuations. If somebody isn't thinking in terms of implementations, continuations are just "you pass in who to return the result to, as an argument." e.g. If it succeeds, tell this function the result, otherwise tell this function the error. Yet another case of making concepts hard by knowing too much.
- dublinclontarf 16y ago
  Why that is the best simple explanation of continuations I have come across yet. Totally right, it's like thinking about how you are able to walk, if you do it trips you up. Dont think about the details just the concepts.
  - silentbicycle 16y ago
    It's not something people are used to talking explicitly about; it's so ingrained that stuff returns directly to what called it that it never occurs to them. Exceptions are probably the only exception, but I'm not aware of any language besides Common Lisp where an error doesn't unwind the stack - "an exception makes it return several levels up, where the last handler was defined" still fits within a fundamentally stack-based mental model.
    - infinite8s 16y ago
      Actually, that description of exceptions requires a stack-based mental model. With true continuations, you have other possibilities for handling the exception (see for example Haskell).
      - silentbicycle 16y ago
        That's _exactly_ my point. Exceptions (as typically implemented) fit within a stack-based mental model, Common Lisp's resumable exceptions and first-class continuations do not.
btilly 16y ago
It sounds like your professors suffer from the same problem that many math professors do. Namely lecturing to an imagined audience that is conversant with intellectual debates that the actual audience is entirely ignorant of. In the case of math professors this results in lectures where the professor gives detailed proofs despite knowing that nobody in the class followed it, you can't dare test it, and the whole class wondered what the point was. Yet the proofs are rigorous and address points that it took mathematicians decades to figure out. In the case of your CS profs, in the 1980s I imagine that they were coming out of an era where many computer languages did not support recursion at all because doing so was too inefficient. And therefore they focused very much on exactly how you could implement them, and what the efficiency was.
sirclueless 16y ago
The problem with doing away with the implementation specific details of recursion is that these details are inextricably linked to the correctness of your program in most languages. The fact is, even with modern optimizing compilers that prove all sorts of correctness theorems about transformations, stack overflows will occur in recursive programs if you aren't constantly aware of their existence. You always have to code recursive programs defensively. A program coded like "recurse(n-1)" will probably blow its lid if you pass in 1,000,000 as the parameter while "for (i=0; i<N; i++)" will happily chug away a billion times. Or worse, if you call "recurse(n-1)" twice in the same function and then pass in a measly value of 100 as the parameter, you will be waiting for the program to terminate on your deathbed. Explaining why these differences are important to a beginning student, let alone teaching them how to avoid them on their own, is a task that can only get in the way. Avoiding recursion for a while is a much better way to make first few attempts at independent coding not go up in flames.
- eru 16y ago
  I just tried, and ghci (i.e. Haskell) does not blow up when confronted with > let f n = if n > 0 then n + f (n - 1) else 0 > f 1000000
  - sbochins 16y ago
    ...which is why we should be using lazy languages.
    - eru 16y ago
      Although lazyness is the usual suspect, it has nothing to do with this.
primodemus 16y ago
Robert Harper from CMU, eloquently expresses the same notion: "One of the classic pitfalls of teaching recursion is to try to explain it by referring to some mysterious entity called a “stack” that is absolutely invisible in the program you write. There’s a long song and dance about “frames” and “procedure calls” and “pushing” and “popping” things on this “stack” of which the professor speaks, and no one understands a damn thing. It all sounds very complicated, and impressive in a way, but if there’s one thing people learn, it’s to stay the hell away from it! And in doing so, students are robbed of one of the most powerful and useful programming tools available to them, the key to writing clean, reliable code". more: http://existentialtype.wordpress.com/2011/03/21/the-dog-that-didnt-bark/ http://existentialtype.wordpress.com/2011/03/21/the-dog-that...

by pg 16y ago

leif 16y ago

Why, though, do they think of a function as a machine for doing something? Because we tell them so. Before starting any standard CS curriculum (ignoring, for a moment, self-taught hackers), the only place a student should have heard about "functions" is in math class---where they are definitions. They get to intro Java and we tell them "no, no, that's not a function, this is a function, look, it's got variables and for loops and increments and a bunch of returns all through it, this is the real stuff, remember it!" We un-teach them about recursion, and later, when we try to re-teach it to them, we have to undo all of our previous work. In the past, there was considerable merit to un-learning the inefficient definition-style functions and learning to think closer to the machine. Today, I think there's a lot more to be gained by sticking with the math-style function-as-a-definition, because we have efficient abstractions to deal with it, but of course, this is one of the friendliest forums for that sort of philosophy. FWIW, I propose that all of academia make a distinction between pure, recursive, definition-style "functions", and imperative, stateful "methods". Probably won't catch on :-/

eru 16y ago
Your "methods" have also been called "procedures".
- leif 16y ago
  sure. pick one and make people use it

silentbicycle 16y ago

Yes, recursion is tied up with baggage about stack allocation. If recursion is approached as inductive reasoning, those objections never occur. This particularly applies to tail-call optimizations and continuations. If somebody isn't thinking in terms of implementations, continuations are just "you pass in who to return the result to, as an argument." e.g. If it succeeds, tell this function the result, otherwise tell this function the error. Yet another case of making concepts hard by knowing too much.

dublinclontarf 16y ago
Why that is the best simple explanation of continuations I have come across yet. Totally right, it's like thinking about how you are able to walk, if you do it trips you up. Dont think about the details just the concepts.
- silentbicycle 16y ago
  It's not something people are used to talking explicitly about; it's so ingrained that stuff returns directly to what called it that it never occurs to them. Exceptions are probably the only exception, but I'm not aware of any language besides Common Lisp where an error doesn't unwind the stack - "an exception makes it return several levels up, where the last handler was defined" still fits within a fundamentally stack-based mental model.
  - infinite8s 16y ago
    Actually, that description of exceptions requires a stack-based mental model. With true continuations, you have other possibilities for handling the exception (see for example Haskell).
    - silentbicycle 16y ago
      That's _exactly_ my point. Exceptions (as typically implemented) fit within a stack-based mental model, Common Lisp's resumable exceptions and first-class continuations do not.

btilly 16y ago

It sounds like your professors suffer from the same problem that many math professors do. Namely lecturing to an imagined audience that is conversant with intellectual debates that the actual audience is entirely ignorant of. In the case of math professors this results in lectures where the professor gives detailed proofs despite knowing that nobody in the class followed it, you can't dare test it, and the whole class wondered what the point was. Yet the proofs are rigorous and address points that it took mathematicians decades to figure out. In the case of your CS profs, in the 1980s I imagine that they were coming out of an era where many computer languages did not support recursion at all because doing so was too inefficient. And therefore they focused very much on exactly how you could implement them, and what the efficiency was.

sirclueless 16y ago

The problem with doing away with the implementation specific details of recursion is that these details are inextricably linked to the correctness of your program in most languages. The fact is, even with modern optimizing compilers that prove all sorts of correctness theorems about transformations, stack overflows will occur in recursive programs if you aren't constantly aware of their existence. You always have to code recursive programs defensively. A program coded like "recurse(n-1)" will probably blow its lid if you pass in 1,000,000 as the parameter while "for (i=0; i<N; i++)" will happily chug away a billion times. Or worse, if you call "recurse(n-1)" twice in the same function and then pass in a measly value of 100 as the parameter, you will be waiting for the program to terminate on your deathbed. Explaining why these differences are important to a beginning student, let alone teaching them how to avoid them on their own, is a task that can only get in the way. Avoiding recursion for a while is a much better way to make first few attempts at independent coding not go up in flames.

eru 16y ago
I just tried, and ghci (i.e. Haskell) does not blow up when confronted with > let f n = if n > 0 then n + f (n - 1) else 0 > f 1000000
- sbochins 16y ago
  ...which is why we should be using lazy languages.
  - eru 16y ago
    Although lazyness is the usual suspect, it has nothing to do with this.

primodemus 16y ago

Robert Harper from CMU, eloquently expresses the same notion: "One of the classic pitfalls of teaching recursion is to try to explain it by referring to some mysterious entity called a “stack” that is absolutely invisible in the program you write. There’s a long song and dance about “frames” and “procedure calls” and “pushing” and “popping” things on this “stack” of which the professor speaks, and no one understands a damn thing. It all sounds very complicated, and impressive in a way, but if there’s one thing people learn, it’s to stay the hell away from it! And in doing so, students are robbed of one of the most powerful and useful programming tools available to them, the key to writing clean, reliable code". more: http://existentialtype.wordpress.com/2011/03/21/the-dog-that-didnt-bark/ http://existentialtype.wordpress.com/2011/03/21/the-dog-that...