Stop Telling Students Recursion is Hard
jinfiesto.posterous.com
jinfiesto.posterous.com
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.
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.
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.
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.
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 :-/
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.
> let f n = if n > 0 then n + f (n - 1) else 0
> f 1000000And 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.
I think I had a CS prof who introduced recursion with this phrase, and it sounds like the class schedule matches up...
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.
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.
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.
But people do implicitly understand recursion. Your ancestors are your parents and their ancestors. Your descendants are your children and their descendants. Most people understand the previous two sentences.
> As soon as they figure out that for and while loops are sufficient to express all the programming ideas they can come up with
There are plenty of problems for which recursion is the most natural solution. For example, building HTML for nested comments is easy with recursion and damned difficult without.
>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.
This is contrary to my firsthand experience. As a teenager, I did BASIC programming. I had a magazine (printed on paper; I'm dating myself) with a BASIC program listing that generated mazes. I could not wrap my head around what that program was doing. At some point my parents bought me FORTH, which does have recursion. That was sufficiently expressive for me to understand how to generate a maze, and even write the program myself without an example. Yes, it's possible to express any programming idea with loops, but many ideas are much more easily expressed with recursion.
So if your kid was thinking recursively, the last "up" operation would be part of the first "up" operation and also part of every intervening "up" operation. If you asked your kid on the last step of a twelve-step staircase how many "up" she was doing, she presumably wouldn't answer "twelve;" she would answer "one." Would that be because she performed the obvious optimization of a tail-recursive function, or because she wasn't actually thinking recursively?
0 = {}
n + 1 = n ∪ {n}
3 = 2 ∪ {2} = 1 ∪ {1} ∪ {1 ∪ {1}} etc.
f(1) = 1
f(n+1) = (n+1) * f(n)
If you believe that people naturally conceive of recursive ideas, then what happens when their ideas aren't easily transformed to a tail-recursive form? Is that why babies cry all the time? Perhaps by the time we are small children we have learned to subconsciously discard all recursive ideas that we can't transform into a tail-recursive form? If there is a part of my brain that naturally generates tail-recursive solutions to problems but won't plague me with frustrating non-tail-recursive solutions, I would love to tap into it.
(define (up)
(and (stair-in-front-of-me)
(walk stair)
(up))) while there are stairs in front of me
climb one stair
The word "while" implies thinking about a range of time from beginning to end. In contrast, the non-"while" version lets you stay in the moment. It's a conceptually simpler program, up until the point we use that fancy mathematical r-word to describe it.
I disagree. The word "while" does connote time, but it's just the word chosen by early programmers to describe a process of performing an action immediately depending on current conditions, with no knowledge of history. Recursion amounts to the same thing -- after you make the mental leap of a tail-recursive optimization. When you climb the next step, you're climbing it because it's part of the definition of climbing the rest of the steps, which was part of the definition of climbing the rest of the steps when you were on the previous step. As I pointed out in another comment, when you're climbing the last step of a twelve-step staircase, you're actually performing twelve "climb up the steps" operations that are nested like Russian dolls. Thinking recursively is only simple when you learn to mentally simplify all of that, basically to think in terms of the "same machine code" you mention in your comment. I don't think we arrive at that "machine code" starting from a recursive definition of climbing the stairs. It seems much more likely that we figure out the implementation (the while loop) long before we figure out (if we ever do) that we can derive that implementation from a recursive definition of the task.
def up():
if not at top stair:
up()
It seems to me that "climb one stair as long as there are stairs" is a conceptually simpler definition than "climb one stair and then climb the stairs if there are still stairs."
I think my point still is I don't see how you're differentiating between these procedures in your daughter's mind— why you're assuming that "up" means "I need to climb all of these stairs" rather than "I need to climb this one stair in front of me."
(If indeed it makes sense to model human behavior either way at all; it probably makes the most sense to think of it more as an event loop...)
That's a while loop.
Or tail-recursion. I think a more natural example of recursion would be solving a maze. To solve the maze we pick a path we think likely to lead to the exit, if we reach a dead end we back track and try another path.
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 -- 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.
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.
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.
"When n is a positive integer, exponentiation corresponds to repeated multiplication."
And then an equation that suggests an iterative approach.
The point with my C function is that it's certainly simple to do in a non-functional language.
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.
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.
Am I missing anything?
EDIT: I wrote this before reading the article
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)>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?
By contrast, in order to calculate the number of nodes in a binary tree, you would do
(nodes (tree)
(if (tree? tree)
(1+ (nodes (left-node tree))
(nodes (right-node tree)))
0))
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.
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.
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.
In an iterative language it's a for loop and then calling the function on each of the children. In a Lisp it's calling it's self on the child and next node.
PS: Showing someone they can transform a recursion function into a while loop if they keep track of their own stack seems to help. Yea, you can write it that way, but recursion really is simpler. (This also helps explain what a stack really is.)
def bfs(search_node, nodes_to_visit):
node = nodes_to_visit.pop()
if node == search_node:
return node
else:
nodes_to_visit.extend(node.neighbors)
return bfs(search_node, nodes_to_visit)
bfs(search_node, [root_node])After you fix that minor bug, you'll find that your code crashes for trees with over 1000 nodes. That is also easy to fix. But in any language without tail recursion, your implementation hits the stack hard. Which in many multi-threaded environments may not be not a wise thing to do.
All that said, I submit that you easily think of that version because you're familiar with how the recursive solution manages the stack. If you're familiar with that, then switching from dfs to bfs is just a question of replacing a stack with a queue. Compare:
def dfs(search_node, root_node):
nodes_to_visit = [root_node]
while 0 < len(nodes_to_visit):
node = nodes_to_visit.pop()
if node == search_node:
return node
else:
nodes_to_visit.extend(node.children)
return None
def bfs(search_node, root_node):
nodes_to_visit = [root_node]
while 0 < len(nodes_to_visit):
node = nodes_to_visit.pop(0)
if node == search_node:
return node
else:
nodes_to_visit.extend(node.children)
return None
def dfs_recursive(search_node, root_node):
if search_node == root_node:
return root_node
for child_node in root_node.children:
answer = dfs_recursive(search_node, child_node)
if answer is not None:
return answer
return None
def bfs_recursive(search_node, root_node):
nodes_to_visit = []
def _recurse():
if 0 == len(nodes_to_visit):
return None
node = nodes_to_visit.pop()
if node == search_node:
return node
else:
nodes_to_visit.extend(node.children)
return _recurse()
return _recurse()Luckily I was able to edit my node to hide my variation of the error.
Most examples are toys (fib, towers of hanoi, maze solving) or problems that are already solved, sorting, searching, etc.
"Did you mean: recursion"A recursive function call is conceptually no different than a regular function call.
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.
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.
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.
That's not the whole story. There's more to recursion than that. You can have mutual recursion, and recursion in things other than functions: e.g. data structures, or the structure of the Mandelbrot set or that of the fern-like fractals.
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.Perhaps it isn't taught properly? When you're just starting out with it, there really isn't much to teach though.