10 ms·

Stop Telling Students Recursion is Hard

83 points by jinfiesto 16y ago

goalieca 16y ago
I think the main fault of recursion is that students end up with "stack overflow". The JVM and C++ also don't have tail recursion. Performance is really the biggest perception difficulty. Would also help if students learned about inductive proofs in mathematics earlier on.
kgo 16y ago
I don't think that teachers are telling students recursion is hard. I think that through observations, good teachers who have taught for many years have seen that many, many students will just never get recursion. And that's the basis of teachers saying that recursion is hard.
- Retric 16y ago
  The idea behind recursion is I have X, if I know Y then this would be easy. But, picking the correct Y and finding a simple path to get Y is hard for many people. Consider something as simple as factorials. 1! = 1 and N! = N * N-1! but try to code it as: N! = N! / 1! * 1 = N! / 2! * 2 = N! / 3! * 6. Then with a lot of time and effort they get something that works, but it's not intuitive.
  - hugh3 16y ago
    Perhaps the other problem is that it's not obvious to students what the point of doing things recursively is. OK, it can shave a few characters off your factorization code. Or your Fibonacci code. That's neat, but why get excited?
    - teach 16y ago
      I usually show them a recursive Towers of Hanoi solver. It's alarmingly simple (fewer than 10 LOC) and most of them can't even imagine how to write it iteratively. I tell them that recursive code is rarely better than iterative code, but for certain types of problems, it's SO much easier to come up with a recursive solution that it's worth knowing how to do.
      - sid0 16y ago
        I tell them that recursive code is rarely better than iterative code As a general statement, this is wrong. Recursive code is almost always better than imperative code in languages designed to encourage recursion -- I'm thinking of functional languages here, of course. Please qualify your statements to your students, lest they get the idea that it is a problem with recursion as a principle rather than a problem with the language they're working in.
      - mdg 16y ago
        I am not sure if I understand recursion or not. My definition of recursion is a function that calls itself repeatedly until an exit condition occurs (the first chapters of little schemer define this as an empty list). If the exit condition never occurs, and the computer lacks infinite computing power, you will probably get a stack overflow. As far as I can tell, recursion and a for-loop accomplish the same thing. Am I missing anything? EDIT: I wrote this before reading the article
        spacemanaki 16y ago
        You aren't missing anything, but recursion can get more complicated. In the case of towers of Hanoi, or recursion on trees, the iterative version using a for-loop becomes substantially more complicated than the recursive version. Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So in Scheme this will actually produce an infinite loop with no stack overflow: (define (loop) (loop)) (loop)
        mdg 16y ago
        Thanks for your answer. >Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So that is why people make such a big deal about tail-call optimization? Because it prevents stack overflow?
        sid0 16y ago
    - TillE 16y ago
      Solving a maze is a classic. The recursive solution is the obvious/intuitive one.
      - hugh3 16y ago
        Again, mazes and Towers of Hanoi are neat, but still not exactly what you'd call problems with real-world applicability. There must be some out there -- some types of parsers, perhaps? Are there any matrix operations which are best done recursively? I just think that recursion falls into the category of things that professors think are neat rather than the category of things that are useful to students. Some students will love that kind of thing, others will wonder what the hell the point is.
        zheng 16y ago
        Yes, exactly, recursive descent parsers are what they sound like. I'm not very up on other types of parsers, but this is the kind I learned about, and I would say they are very intuitive. http://en.wikipedia.org/wiki/Recursive_descent_parser http://en.wikipedia.org/wiki/Recursive_descent_parser
        djjose 16y ago
        One of the projects in my CS program using recursion was a 6-degrees of Kevin Bacon game. It was neat and real-world practical IMO.
        btilly 16y ago
        Any "divide and conquer" algorithm is likely to be recursive. Thus, for instance, the FFT, the Karatsuba multiplication algorithm for large integers, Strassen's matrix multiplication algorithm for matrices and the like are all recursive. Moving on, dynamic programming is a very important technique. About half the time it is easier for me to figure out a dp solution by writing a recursive solution with memoization than it is to build the solution bottom up. The single most studied problem in computer science is sorting, for the simple reason that a surprising fraction of computing time spent is spent doing sort operations. Virtually every efficient sort algorithm uses recursion somewhere. The fact that a lot of students won't go on to use recursion doesn't mean that it isn't a very useful technique.
teach 16y ago
It's funny. I've JUST finished spending a week or so on recursion with my students. The FIRST thing I did was have the entire class repeat after me: "Recursion isn't hard. It's just different." And I've been teaching CS at the high-school level for 13(?) years now, and I've never had a student who just couldn't get recursion. On the contrary, most of the them pick it up pretty quickly. There's initial confusion, followed by the flash of insight, and then they're pretty much golden.
- calebmpeterson 16y ago
  As a programmer of more than a decade who fell in love with CS in high school, thank you for teaching the topic to others!
- burgerbrain 16y ago
  Long shot here, but do you happen to teach at a certain engineering school in Philadelphia? I think I had a CS prof who introduced recursion with this phrase, and it sounds like the class schedule matches up...
- jinfiesto 16y ago
  I've found this to be the case too, I think telling students that recursion is difficult artificially limits their ability to comprehend it.
jchonphoenix 16y ago
A lot of the disagreement here comes from what people consider recursion. As in all things, the basic idea behind recursion is quite simple to understand. It's just a function calling itself. There are, however, some non-trivial uses of recursion such as quicksort and analyzing its runtime. Thus, to say simple recursion isn't hard is true. But I'm sure that we can all find a recursive problem that we wouldn't consider easy.
- cdavid 16y ago
  Agreed - the problem is not recursion, but that it becomes useful for actual complex problems. I understand recursion pretty well at a conceptual level (my background is math, mostly self-taught for CS), but I have a hard time using it for programming. Sure, fibonacci or quicksort are simple, but tree recursion or application to string processing (e.g. for edit distance compuation) is quite harder.
  - rimantas 16y ago
    I am the only one who gets upset when fibonacci sequence calculation is used as an example of recursion? Are there other possible examples which are simpler than quicksort, but actually make sense if done with recursion instead of simple loop?
    - cdavid 16y ago
      No, I think it is a terrible example at so many levels it is not even funny. The only interesting thing about that example is how almost any other solution is much better. I would consider quicksort to be a quite simple example if you use a high level language. But search in binary search tree and similar tree/graph traversal are maybe better examples, in the sense that most people would find recursion to be more natural than any iterative solution.
- athom 16y ago
  Actually, this is not correct. While recursion is typically implemented in the form of a function which calls itself, that is not exactly what recursion means. In fact, "recursion" derives from "recur", which simply means to repeat, or re-occur, which, when you look at it, is exactly what a "recursive" function is designed to do (without all that messy for/next, do/while jazz). Calling itself is just a particularly clever, interesting, and elegant way to do that. To really illustrate the point of recursion, consider showing your students one of the simplest recursive algorithms out there. You can find it on the back of many shampoo bottles: * Lather. * Rinse. * Repeat.
zheng 16y ago
Am I along in never being "taught" recursion? I mean, throughout my curriculum, I've used recursion many times and dealt with everything from fibonacci to quicksort, but never once have I sat through even part of a lecture on "Recursion". Among my peers, I don't think anyone really has an issue with recursion or how it works. Harder to debug possibly, but everyone "gets" it, I feel.
- eru 16y ago
  Shouldn't it be easier to debug, because you have stack traces?
StanDarsh 16y ago
Interesting article on recursion... http://tenaciousc.com/?p=1000 http://tenaciousc.com/?p=1000
ohyes 16y ago
It might be easier to teach them about functions that can call themselves first; and then explain the concept of recursion in the context of that (or just that it is called 'recursion'). A recursive function call is conceptually no different than a regular function call.
- eru 16y ago
  There's more to recursion than functions. Data types (like linked lists) can also be recursive.
satoimo 16y ago
Getting tail recursion right IS hard.
oniTony 16y ago
Interestingly enough, in curriculums that start out with functional languages (e.g. Scheme) students have little trouble with recursion... and then consider iterative loops to be "hard".
- Sherlock 16y ago
  Wow, that's surprising, I'd love to hear about some (anecdotal) evidence supporting this.
  - eru 16y ago
    I heard Matthias Felleisen saying the same.
  - SkyMarshal 16y ago
    In college they tried to teach us recursion using C and I didn't get it. Later I discovered The Little Schemer and SICP and it just clicked. It's easier to do in Scheme/Lisp, and those books also explain it better. There's one anecdote. :)
colomon 16y ago
On the one hand, I'm in total agreement that we shouldn't tell students recursion is hard. It's a very natural analog to proof by induction, after all. It's an important basic component of programming. On the other hand, "IMHO, recursion is much more natural than iteration and ought to be taught first" is just nuts. I mean, look at the first definition of his example function at http://en.wikipedia.org/wiki/Exponentiation http://en.wikipedia.org/wiki/Exponentiation -- it's iteration, pure and simple. And in most non-functional languages, it's trivial to implement that way, and will probably be more efficient than a recursive solution.
- jinfiesto 16y ago
  I don't think the example I've given is iterative. It generates a recursive process. You're right on a different point though, this example is much more efficiently implemented iteratively. The point was to illustrate that writing recursive functions is not difficult. I guess we don't see eye to eye on recursion being taught first. :p In my opinion, recursions analog to "the real world" is much more intuitively obvious than iteration.
  - fferen 16y ago
    I think parent was referring to the definition on the Wikipedia page: "When n is a positive integer, exponentiation corresponds to repeated multiplication." And then an equation that suggests an iterative approach.
    - colomon 16y ago
      Exactly. Good catch.
  - charlieflowers 16y ago
    Actually, I think your example generates an iterative process, not a recursive process. In other words, according to what I read in SICP recently (working through it the first time), I think your example is a recursive function that generates an iterative process. It's an iterative process because incoming function arguments capture a snapshot of its state at any point, and therefore you don't need state that exists deeper on the call stack. The upshot is that iterative processes are more efficient in terms of how much stack space they use. Not trying to nitpick -- I enjoyed your post and it is still relevant. Also, I could be wrong, so someone please correct me if so.
grigory 16y ago
In my first year programming course, our prof spent 10-15 minutes at most talking about recursion. I was already familiar with it, but my classmates (mostly non-CS majors) had no problems understanding the concept. Since that experience I'm always slightly amused when I hear people saying that teaching basics of recursion is hard. Perhaps it isn't taught properly? When you're just starting out with it, there really isn't much to teach though.
- ern 16y ago
  You say they "understood" the concept. Was this understanding tested in some way?
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
irahul 16y ago
When learning recursion, there aren't much practice problems people do in imperative languages. Most of the imperative languages don't have tail call optimization and the prevalent culture is to use iteration. That said, there are some problems for which the iterative solution won't be straight forward viz. quicksort, mergesort, binary tree traversal etc etc. But the issue is when a student not very familiar with recursion stumbles upon these, he has a hard time understanding them. I learned recursion and manual recursion removal in C. I already understood recursion when I read "The Little Schemer", but it still managed to change my perception. I highly recommend it, regardless of whether you are going to work in Scheme(most likely no) or not.
- cygwin98 16y ago
  Same experience here, though I learned recursion in Pascal. Maybe it's just me, it just feels awkward when you do recursion in imperative languages. For the past two years, I've been playing/working with functional languages, firstly Erlang or more recently F#, as well as functional programming in C#, and start to appreciate the power of FP. Recursion is also used more often as it just feels natural there when you do recursion in FP.
- SkyMarshal 16y ago
  /second TLS. Most of the book is on recursion, and uses a Socratic teaching method to both explain and reinforce it brilliantly.
finin 16y ago
LOGO, a programming language for teaching computing to young children, uses recursion as its fundamental control structure. My kids studied it successfully in a Philadelphia public school on C64s in the 1980s.
dkarl 16y ago
Recursion is a natural idea. When humans perform repetitive tasks, we don't assign state variables, and we generally don't keep counters. We just keep doing the same thing over and over until we arrive at some kind of terminating condition. That's a while loop. To eat a bowl of Cheerios, keep spooning Cheerios into your mouth while there are more Cheerios in the bowl. Telling students that recursion is hard isn't a good idea, but telling them that it's a familiar idea that they already implicitly understand isn't a good idea either. The way people normally conceive of iterative processes does not contain the essential element of recursion: that something is used in its own definition. The recursive definition of eating a bowl of Cheerios is: if there are Cheerios in the bowl, you're done; otherwise, spoon some Cheerios into your mouth and then eat the bowl of Cheerios. Most people encountering recursion in a class have never thought that way before. (Jokes are perhaps the only counterexample, though I can't think of any right now.) That doesn't mean it's hopeless. As another poster said, recursion isn't difficult. It's a simple idea. It's just different. "Different" has big consequences, though. In interviews, I give candidates a programming problem that is solvable using recursion. Very few people come close to solving it -- mostly I judge people by how they approach the problem, not whether they eventually figure out the solution -- but usually, after figuring out (perhaps with lots of prompting) that the problem can't be solved with nested for loops, they manage to volunteer the word "recursion." Now here's the kicker: about half the candidates who say they're going to solve the problem "recursively" do not actually attempt a recursive solution, not even an incorrect one. They seem to associate recursion with defining functions, because they begin their "recursive" solution by defining a function. However, they do not define a function that calls itself. They do not define mutually recursive functions, either. These are applicants for a senior technical position. They aren't washouts, they're people who have had years of development experience at some point in their careers. If half the people who are technically inclined enough to choose a career in development, stick with it for many years, and advance to a senior position have a hard time with recursion.... No, if those people don't even understand the basic idea behind one of the most famous concepts in their field (a concept whose name they can still recall despite never or rarely needing to use it since college) then it is not a way of thinking that people develop outside of math and computer science. It isn't a skill that people naturally apply in other domains but have a hard time applying to programming. It isn't just a problem of making a connection between the word "recursion" and a cognitive skill that everybody has. No, it's an alien way of thinking that only becomes familiar through sufficient practice. Until it becomes a natural way of thinking, it's just a definition that can be forgotten as easily as forgetting the year the Magna Carta was signed. Iterative solutions do follow familiar thinking patterns. Write a sentence on the chalkboard 100 times. Chop on the tree until the tree falls down. Check every line in your credit card statement. Let's drink every one of these bottles of beer. When students write a program that has a for loop or a while loop, they're expressing something familiar they've done countless times before. They're just doing it in a new and unfamiliar form. Even many of the common constructs in functional programs have been drilled into kids since grade school. Map: examine every child's head for lice. Filter: make a list of everyone who didn't turn in their permission slip. Those ways of thinking are thoroughly ingrained, and students who drop CS 101 and become art history majors won't forget how to think that way just because they don't write programs. Teaching kids recursion before iterative constructs might be a good idea on balance, but let me play devil's advocate. Teaching iterative constructs first has one big advantage: while the students are grappling with the novelty of describing a process in the form of code, at least they are describing familiar processes they understand. Teaching them recursion first means they will be trying to learn the mechanics of writing a program at the same time they're trying to learn recursion. When they have difficulties, they might not be able to figure out which concept they're getting wrong. Why not teach them to program iterative constructions first, and then, after they have some confidence with the task of writing a complex program in a programming language, let them tackle the challenge of recursion? That way they always have something familiar to lean on while they're struggling. I sympathize with the basic motivation whenever anyone proposes teaching recursion before iteration, which is to keep the kids dependent on their skill with recursion. As soon as they figure out that for and while loops are sufficient to express all the programming ideas they can come up with, they won't want to learn anything else. If recursion is their only tool for expressing simple programs, they'll keep struggling with it until they learn it. Unfortunately, that's not going to work. Kids have always been able to read ahead in the book, and now the first place they'll look is the internet, where other students will let the cat out of the bag. You're going to have to persuade them that it's worth struggling with until they understand it.
ajg1977 16y ago
Probably the best HN comment on recursion: http://news.ycombinator.com/item?id=2440869 http://news.ycombinator.com/item?id=2440869
- deleted 16y ago
  [deleted]
- deleted 16y ago
  [deleted]
- endian 16y ago
  http://www.google.com/search?q=recursion http://www.google.com/search?q=recursion "Did you mean: recursion"
mzl 16y ago
When teaching our students concurrent programming using Erlang we never actually mentioned recursion and state immutability. With some careful hand-holding in the first exercises, most of the students seemed to be able to do fine. During three years of teaching the class, only two students ever asked me about immutability ("why can't I change the value of this variable?"). Recursion went similarly unnoticed, it was just the way one programmed in Erlang. Still, a lot of the code produced in the assignments was not very good, but that is to be expected from the course level and the students. There are two main reasons why I think that most students picked it up without too big troubles. First is that we are just using these things as part of a language while focusing on other topics (concurrent programing). The other is that Erlang is language with such a different syntax from the normal Java-fare that one naturally expects to not be able to do things in the same way.
- SkyMarshal 16y ago
  That's probably the best approach. If you tell students it's 'not hard', they'll immediately suspect your motives and come to the conclusion it actually is hard. If you tell them it's hard, most will believe you. Probably better just to not qualify it and slip it into the lesson when they're not expecting it.
d135-1r43 16y ago
Telling them that it is cost intensive would be better!
- adrianN 16y ago
  That depends on how you write your recursion, what your compiler does with it and what you use as cost function (programmer productivity?). That's too many 'depends' to tell students about, I think.
theclay 16y ago
Recursion is harder in some languages than others (e.g. python--a commonly recommended beginner language--where recursion is deliberately broken)
gte910h 16y ago
I always found talking about stories about stories about stories a very easy way to get it across. Humans intrinsically get stories.

83 points by jinfiesto 16y ago

I think the main fault of recursion is that students end up with "stack overflow". The JVM and C++ also don't have tail recursion. Performance is really the biggest perception difficulty. Would also help if students learned about inductive proofs in mathematics earlier on.

kgo 16y ago

I don't think that teachers are telling students recursion is hard. I think that through observations, good teachers who have taught for many years have seen that many, many students will just never get recursion. And that's the basis of teachers saying that recursion is hard.

Retric 16y ago
The idea behind recursion is I have X, if I know Y then this would be easy. But, picking the correct Y and finding a simple path to get Y is hard for many people. Consider something as simple as factorials. 1! = 1 and N! = N * N-1! but try to code it as: N! = N! / 1! * 1 = N! / 2! * 2 = N! / 3! * 6. Then with a lot of time and effort they get something that works, but it's not intuitive.
- hugh3 16y ago
  Perhaps the other problem is that it's not obvious to students what the point of doing things recursively is. OK, it can shave a few characters off your factorization code. Or your Fibonacci code. That's neat, but why get excited?
  - teach 16y ago
    I usually show them a recursive Towers of Hanoi solver. It's alarmingly simple (fewer than 10 LOC) and most of them can't even imagine how to write it iteratively. I tell them that recursive code is rarely better than iterative code, but for certain types of problems, it's SO much easier to come up with a recursive solution that it's worth knowing how to do.
    - sid0 16y ago
      I tell them that recursive code is rarely better than iterative code As a general statement, this is wrong. Recursive code is almost always better than imperative code in languages designed to encourage recursion -- I'm thinking of functional languages here, of course. Please qualify your statements to your students, lest they get the idea that it is a problem with recursion as a principle rather than a problem with the language they're working in.
    - mdg 16y ago
      I am not sure if I understand recursion or not. My definition of recursion is a function that calls itself repeatedly until an exit condition occurs (the first chapters of little schemer define this as an empty list). If the exit condition never occurs, and the computer lacks infinite computing power, you will probably get a stack overflow. As far as I can tell, recursion and a for-loop accomplish the same thing. Am I missing anything? EDIT: I wrote this before reading the article
      - spacemanaki 16y ago
        You aren't missing anything, but recursion can get more complicated. In the case of towers of Hanoi, or recursion on trees, the iterative version using a for-loop becomes substantially more complicated than the recursive version. Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So in Scheme this will actually produce an infinite loop with no stack overflow: (define (loop) (loop)) (loop)
        mdg 16y ago
        Thanks for your answer. >Also, in Scheme and other functional languages, function calls in the tail position are compiled or otherwise treated as jumps. So that is why people make such a big deal about tail-call optimization? Because it prevents stack overflow?
        sid0 16y ago
  - TillE 16y ago
    Solving a maze is a classic. The recursive solution is the obvious/intuitive one.
    - hugh3 16y ago
      Again, mazes and Towers of Hanoi are neat, but still not exactly what you'd call problems with real-world applicability. There must be some out there -- some types of parsers, perhaps? Are there any matrix operations which are best done recursively? I just think that recursion falls into the category of things that professors think are neat rather than the category of things that are useful to students. Some students will love that kind of thing, others will wonder what the hell the point is.
      - zheng 16y ago
        Yes, exactly, recursive descent parsers are what they sound like. I'm not very up on other types of parsers, but this is the kind I learned about, and I would say they are very intuitive. http://en.wikipedia.org/wiki/Recursive_descent_parser http://en.wikipedia.org/wiki/Recursive_descent_parser
      - djjose 16y ago
        One of the projects in my CS program using recursion was a 6-degrees of Kevin Bacon game. It was neat and real-world practical IMO.
      - btilly 16y ago
        Any "divide and conquer" algorithm is likely to be recursive. Thus, for instance, the FFT, the Karatsuba multiplication algorithm for large integers, Strassen's matrix multiplication algorithm for matrices and the like are all recursive. Moving on, dynamic programming is a very important technique. About half the time it is easier for me to figure out a dp solution by writing a recursive solution with memoization than it is to build the solution bottom up. The single most studied problem in computer science is sorting, for the simple reason that a surprising fraction of computing time spent is spent doing sort operations. Virtually every efficient sort algorithm uses recursion somewhere. The fact that a lot of students won't go on to use recursion doesn't mean that it isn't a very useful technique.

teach 16y ago

It's funny. I've JUST finished spending a week or so on recursion with my students. The FIRST thing I did was have the entire class repeat after me: "Recursion isn't hard. It's just different." And I've been teaching CS at the high-school level for 13(?) years now, and I've never had a student who just couldn't get recursion. On the contrary, most of the them pick it up pretty quickly. There's initial confusion, followed by the flash of insight, and then they're pretty much golden.

calebmpeterson 16y ago
As a programmer of more than a decade who fell in love with CS in high school, thank you for teaching the topic to others!
burgerbrain 16y ago
Long shot here, but do you happen to teach at a certain engineering school in Philadelphia? I think I had a CS prof who introduced recursion with this phrase, and it sounds like the class schedule matches up...
jinfiesto 16y ago
I've found this to be the case too, I think telling students that recursion is difficult artificially limits their ability to comprehend it.

jchonphoenix 16y ago

A lot of the disagreement here comes from what people consider recursion. As in all things, the basic idea behind recursion is quite simple to understand. It's just a function calling itself. There are, however, some non-trivial uses of recursion such as quicksort and analyzing its runtime. Thus, to say simple recursion isn't hard is true. But I'm sure that we can all find a recursive problem that we wouldn't consider easy.

cdavid 16y ago
Agreed - the problem is not recursion, but that it becomes useful for actual complex problems. I understand recursion pretty well at a conceptual level (my background is math, mostly self-taught for CS), but I have a hard time using it for programming. Sure, fibonacci or quicksort are simple, but tree recursion or application to string processing (e.g. for edit distance compuation) is quite harder.
- rimantas 16y ago
  I am the only one who gets upset when fibonacci sequence calculation is used as an example of recursion? Are there other possible examples which are simpler than quicksort, but actually make sense if done with recursion instead of simple loop?
  - cdavid 16y ago
    No, I think it is a terrible example at so many levels it is not even funny. The only interesting thing about that example is how almost any other solution is much better. I would consider quicksort to be a quite simple example if you use a high level language. But search in binary search tree and similar tree/graph traversal are maybe better examples, in the sense that most people would find recursion to be more natural than any iterative solution.
athom 16y ago
Actually, this is not correct. While recursion is typically implemented in the form of a function which calls itself, that is not exactly what recursion means. In fact, "recursion" derives from "recur", which simply means to repeat, or re-occur, which, when you look at it, is exactly what a "recursive" function is designed to do (without all that messy for/next, do/while jazz). Calling itself is just a particularly clever, interesting, and elegant way to do that. To really illustrate the point of recursion, consider showing your students one of the simplest recursive algorithms out there. You can find it on the back of many shampoo bottles: * Lather. * Rinse. * Repeat.

zheng 16y ago

Am I along in never being "taught" recursion? I mean, throughout my curriculum, I've used recursion many times and dealt with everything from fibonacci to quicksort, but never once have I sat through even part of a lecture on "Recursion". Among my peers, I don't think anyone really has an issue with recursion or how it works. Harder to debug possibly, but everyone "gets" it, I feel.

eru 16y ago
Shouldn't it be easier to debug, because you have stack traces?

StanDarsh 16y ago

Interesting article on recursion... http://tenaciousc.com/?p=1000 http://tenaciousc.com/?p=1000

ohyes 16y ago

It might be easier to teach them about functions that can call themselves first; and then explain the concept of recursion in the context of that (or just that it is called 'recursion'). A recursive function call is conceptually no different than a regular function call.

eru 16y ago
There's more to recursion than functions. Data types (like linked lists) can also be recursive.

satoimo 16y ago

Getting tail recursion right IS hard.

oniTony 16y ago

Interestingly enough, in curriculums that start out with functional languages (e.g. Scheme) students have little trouble with recursion... and then consider iterative loops to be "hard".

Sherlock 16y ago
Wow, that's surprising, I'd love to hear about some (anecdotal) evidence supporting this.
- eru 16y ago
  I heard Matthias Felleisen saying the same.
- SkyMarshal 16y ago
  In college they tried to teach us recursion using C and I didn't get it. Later I discovered The Little Schemer and SICP and it just clicked. It's easier to do in Scheme/Lisp, and those books also explain it better. There's one anecdote. :)

colomon 16y ago

On the one hand, I'm in total agreement that we shouldn't tell students recursion is hard. It's a very natural analog to proof by induction, after all. It's an important basic component of programming. On the other hand, "IMHO, recursion is much more natural than iteration and ought to be taught first" is just nuts. I mean, look at the first definition of his example function at http://en.wikipedia.org/wiki/Exponentiation http://en.wikipedia.org/wiki/Exponentiation -- it's iteration, pure and simple. And in most non-functional languages, it's trivial to implement that way, and will probably be more efficient than a recursive solution.

jinfiesto 16y ago
I don't think the example I've given is iterative. It generates a recursive process. You're right on a different point though, this example is much more efficiently implemented iteratively. The point was to illustrate that writing recursive functions is not difficult. I guess we don't see eye to eye on recursion being taught first. :p In my opinion, recursions analog to "the real world" is much more intuitively obvious than iteration.
- fferen 16y ago
  I think parent was referring to the definition on the Wikipedia page: "When n is a positive integer, exponentiation corresponds to repeated multiplication." And then an equation that suggests an iterative approach.
  - colomon 16y ago
    Exactly. Good catch.
- charlieflowers 16y ago
  Actually, I think your example generates an iterative process, not a recursive process. In other words, according to what I read in SICP recently (working through it the first time), I think your example is a recursive function that generates an iterative process. It's an iterative process because incoming function arguments capture a snapshot of its state at any point, and therefore you don't need state that exists deeper on the call stack. The upshot is that iterative processes are more efficient in terms of how much stack space they use. Not trying to nitpick -- I enjoyed your post and it is still relevant. Also, I could be wrong, so someone please correct me if so.

grigory 16y ago

In my first year programming course, our prof spent 10-15 minutes at most talking about recursion. I was already familiar with it, but my classmates (mostly non-CS majors) had no problems understanding the concept. Since that experience I'm always slightly amused when I hear people saying that teaching basics of recursion is hard. Perhaps it isn't taught properly? When you're just starting out with it, there really isn't much to teach though.

ern 16y ago
You say they "understood" the concept. Was this understanding tested in some way?

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

irahul 16y ago

When learning recursion, there aren't much practice problems people do in imperative languages. Most of the imperative languages don't have tail call optimization and the prevalent culture is to use iteration. That said, there are some problems for which the iterative solution won't be straight forward viz. quicksort, mergesort, binary tree traversal etc etc. But the issue is when a student not very familiar with recursion stumbles upon these, he has a hard time understanding them. I learned recursion and manual recursion removal in C. I already understood recursion when I read "The Little Schemer", but it still managed to change my perception. I highly recommend it, regardless of whether you are going to work in Scheme(most likely no) or not.

cygwin98 16y ago
Same experience here, though I learned recursion in Pascal. Maybe it's just me, it just feels awkward when you do recursion in imperative languages. For the past two years, I've been playing/working with functional languages, firstly Erlang or more recently F#, as well as functional programming in C#, and start to appreciate the power of FP. Recursion is also used more often as it just feels natural there when you do recursion in FP.
SkyMarshal 16y ago
/second TLS. Most of the book is on recursion, and uses a Socratic teaching method to both explain and reinforce it brilliantly.

finin 16y ago

LOGO, a programming language for teaching computing to young children, uses recursion as its fundamental control structure. My kids studied it successfully in a Philadelphia public school on C64s in the 1980s.

dkarl 16y ago

Recursion is a natural idea. When humans perform repetitive tasks, we don't assign state variables, and we generally don't keep counters. We just keep doing the same thing over and over until we arrive at some kind of terminating condition. That's a while loop. To eat a bowl of Cheerios, keep spooning Cheerios into your mouth while there are more Cheerios in the bowl. Telling students that recursion is hard isn't a good idea, but telling them that it's a familiar idea that they already implicitly understand isn't a good idea either. The way people normally conceive of iterative processes does not contain the essential element of recursion: that something is used in its own definition. The recursive definition of eating a bowl of Cheerios is: if there are Cheerios in the bowl, you're done; otherwise, spoon some Cheerios into your mouth and then eat the bowl of Cheerios. Most people encountering recursion in a class have never thought that way before. (Jokes are perhaps the only counterexample, though I can't think of any right now.) That doesn't mean it's hopeless. As another poster said, recursion isn't difficult. It's a simple idea. It's just different. "Different" has big consequences, though. In interviews, I give candidates a programming problem that is solvable using recursion. Very few people come close to solving it -- mostly I judge people by how they approach the problem, not whether they eventually figure out the solution -- but usually, after figuring out (perhaps with lots of prompting) that the problem can't be solved with nested for loops, they manage to volunteer the word "recursion." Now here's the kicker: about half the candidates who say they're going to solve the problem "recursively" do not actually attempt a recursive solution, not even an incorrect one. They seem to associate recursion with defining functions, because they begin their "recursive" solution by defining a function. However, they do not define a function that calls itself. They do not define mutually recursive functions, either. These are applicants for a senior technical position. They aren't washouts, they're people who have had years of development experience at some point in their careers. If half the people who are technically inclined enough to choose a career in development, stick with it for many years, and advance to a senior position have a hard time with recursion.... No, if those people don't even understand the basic idea behind one of the most famous concepts in their field (a concept whose name they can still recall despite never or rarely needing to use it since college) then it is not a way of thinking that people develop outside of math and computer science. It isn't a skill that people naturally apply in other domains but have a hard time applying to programming. It isn't just a problem of making a connection between the word "recursion" and a cognitive skill that everybody has. No, it's an alien way of thinking that only becomes familiar through sufficient practice. Until it becomes a natural way of thinking, it's just a definition that can be forgotten as easily as forgetting the year the Magna Carta was signed. Iterative solutions do follow familiar thinking patterns. Write a sentence on the chalkboard 100 times. Chop on the tree until the tree falls down. Check every line in your credit card statement. Let's drink every one of these bottles of beer. When students write a program that has a for loop or a while loop, they're expressing something familiar they've done countless times before. They're just doing it in a new and unfamiliar form. Even many of the common constructs in functional programs have been drilled into kids since grade school. Map: examine every child's head for lice. Filter: make a list of everyone who didn't turn in their permission slip. Those ways of thinking are thoroughly ingrained, and students who drop CS 101 and become art history majors won't forget how to think that way just because they don't write programs. Teaching kids recursion before iterative constructs might be a good idea on balance, but let me play devil's advocate. Teaching iterative constructs first has one big advantage: while the students are grappling with the novelty of describing a process in the form of code, at least they are describing familiar processes they understand. Teaching them recursion first means they will be trying to learn the mechanics of writing a program at the same time they're trying to learn recursion. When they have difficulties, they might not be able to figure out which concept they're getting wrong. Why not teach them to program iterative constructions first, and then, after they have some confidence with the task of writing a complex program in a programming language, let them tackle the challenge of recursion? That way they always have something familiar to lean on while they're struggling. I sympathize with the basic motivation whenever anyone proposes teaching recursion before iteration, which is to keep the kids dependent on their skill with recursion. As soon as they figure out that for and while loops are sufficient to express all the programming ideas they can come up with, they won't want to learn anything else. If recursion is their only tool for expressing simple programs, they'll keep struggling with it until they learn it. Unfortunately, that's not going to work. Kids have always been able to read ahead in the book, and now the first place they'll look is the internet, where other students will let the cat out of the bag. You're going to have to persuade them that it's worth struggling with until they understand it.

ajg1977 16y ago

Probably the best HN comment on recursion: http://news.ycombinator.com/item?id=2440869 http://news.ycombinator.com/item?id=2440869

deleted 16y ago
[deleted]
deleted 16y ago
[deleted]
endian 16y ago
http://www.google.com/search?q=recursion http://www.google.com/search?q=recursion "Did you mean: recursion"

mzl 16y ago

When teaching our students concurrent programming using Erlang we never actually mentioned recursion and state immutability. With some careful hand-holding in the first exercises, most of the students seemed to be able to do fine. During three years of teaching the class, only two students ever asked me about immutability ("why can't I change the value of this variable?"). Recursion went similarly unnoticed, it was just the way one programmed in Erlang. Still, a lot of the code produced in the assignments was not very good, but that is to be expected from the course level and the students. There are two main reasons why I think that most students picked it up without too big troubles. First is that we are just using these things as part of a language while focusing on other topics (concurrent programing). The other is that Erlang is language with such a different syntax from the normal Java-fare that one naturally expects to not be able to do things in the same way.

SkyMarshal 16y ago
That's probably the best approach. If you tell students it's 'not hard', they'll immediately suspect your motives and come to the conclusion it actually is hard. If you tell them it's hard, most will believe you. Probably better just to not qualify it and slip it into the lesson when they're not expecting it.

d135-1r43 16y ago

Telling them that it is cost intensive would be better!

adrianN 16y ago
That depends on how you write your recursion, what your compiler does with it and what you use as cost function (programmer productivity?). That's too many 'depends' to tell students about, I think.

theclay 16y ago

Recursion is harder in some languages than others (e.g. python--a commonly recommended beginner language--where recursion is deliberately broken)

gte910h 16y ago

I always found talking about stories about stories about stories a very easy way to get it across. Humans intrinsically get stories.