My high school computer science teacher and I have recently been exchanging e-mails about how I’m doing in college, etc. As is popular in this area, I’m going to be visiting my high school soon to say hi to my old teachers and such. My computer science teacher asked if I’d like to host a short presentation on recursion in one of her intermediate classes. I said sure.
Now, I know what recursion is. I know how to use it.
How do I teach it to a group of intermediate programmers? I can probably explain it and define it, but I want to show some examples, tips, etc. I was thinking of doing it via PowerPoint. I think to illustrate the basics of recursion, I’m going to step through an example Factorial function.
For those of you who have more experience with this sort of thing, any key points I should talk about? Something I might overlook or miss? Things to avoid without going over their heads?
Good idea using a factorial example - it’s a classic. Squares (and cubes, etc.) work well, too.
For a high school class, the only real point I can think of is avoiding an infinite loop. In addition, if they’ve covered arrays, you may want to explain the importance of starting loop counters at “0” (or whatever the beginning of the array is).
One of my HS CS teachers taught us recursion. She showed in the context of walking through all the elements of a tree (this was Pascal, IIRC).
When she showed us how simple the code was, I blurted out something stupid like “THAT can’t work!” I was doing very well in the class, and over-confident. Of course, it worked fine, and I felt like an ass.
One thing that a substitue said in a class I had, as we were all shooting the breeze for a bit, was using an analogy to describe recursion. (It works well to describe modularity as well.)
Picture a large coporation. When you are hired, they hand you a sheet of paper telling you exactly what you do. (Program.) What you need to do your job (inputs), what the results of your work will be (outputs). Your sheet of paper will tell you if you need to contact somone else to get the work done (function call) and what info to pass to them, and what to do with the info (if any) they give back.
For recursion, your sheet of paper will say ‘concentrate only on this part of the problem. Copy this sheet of paper, hire a new person, and give them the copy and the other parts of the problem you aren’t working on (recursion), unless the part of the problem you are working on meets these criteria (stopping case).’ You can’t contiune working until the new hire returns the info you need, so you wait. Eventually, someone will get the part of the problem that meets the base case, so they return their results to the person who hired them, etc., until you get what you need back.
A bit long winded, but it may help for those who need that kind of visulization and the analogy extends to other concepts. (Multi threading: you pass stuff along, and the co-woker works while you are working, etc.)
Fun topic. I would stay away from tree navigation example for that audience. You could lose them easily. Factorial is probably your best bet. A real world example that might help is the Russian matryoshka ‘nesting dolls’ with a piece of paper in each. Here are some pictures http://www.russian-crafts.com/nest/history.html
Another idea is to make up a story about a robot that keeps cloning itself in order to carry out a task.
Also show them an example of Fibonacci series. Granted recursion is very inefficent since it makes so many function calls but it serves its purpose the same. Including a variable trace diagram helps too.
I have taught recursion to thousands of college students and it is a bear. Sure, it’s trivial for me, but for the overwhelming majority of college students, they automatically go into “glassy eye mode” when anything remotely interesting is taught to them. For high school students, the chances that even one of them will understand it is small. So why waste your time?
And in particular, do not under any circumstances give them: factorial, Fibonacci, Towers of Hanoi and such as examples. They are all much easier to solve without recursion, they’ll know it, and boy will it tick them off!
The only good examples are ones that iteratively are helped by a stack. Evaluating postfix expressions, dfs, etc. What are the chances they’ll understand those?
Explain the reasoning behind recursion: to split a large problem into smaller problems whose solutions can be combined into a solution for the original problem.
Then present mergesort. It’s a conceptually simple algorithm, short to code, and intuitive.
Lastly, explain why using recursion to find Fibonacci numbers is awful.
My high school CS teacher read us The Cat in the Hat Comes Back by Dr. Suess to explain recurssion. The Cat in the Hat calls on Cat A, who calls on Cat B, who calls on Cat C, all the way down to little Cat Z. I always thought that was a really fun way of beginning that lesson.
Oh, give me a break. There’s nothing worse than a teacher who thinks his audience is full of retards. People like you are one of the reasons I got so fed up with higher education the first time around. Perhaps the reason your students went into “glassy eye mode” is because you did such a crappy job of explaining an overwhelmingly simple concept.
There is nothing complicated about recursion, and nothing that can’t easily be explained to high school students. Further, chances are good that high school students taking a CS class probably are actively interested in programming anyway.
My advice is to stay conceptual; avoid the mathematical consequences and analysis and just show a simple recursive task graphically. For example, traversing a binary tree. You don’t even need to show any code. Just demonstrate how the problem is solved by breaking it up into similar smaller problems.
The first bit of recursive programming I did was a maze-solver. The set-up is a bit intense but shouldn’t be beyond anybody who’s been introduced to 2-dimensional arrays (made up of elements that describe which other elements they can legally reach). You just have to translate a graph-paper maze into the array, then the move function would be something like this:
if (I can move to another element)
{
for (element in elements I can move to)
{
if (element == exit) return 1;
i = move(next element);
if ( i == 1) /* found exit down that path*/ return 1;
}
}
return 0;
Of course, add prints and things to show how it’s testing it’s way through the maze. It’s a good example because you can start really simply (4X4 maze or something), it’s easy to relate to on a real-world level, it’s not obvious how you solve the problem without recursion, and it’s a lot more interesting to more people than a purely mathematical exercise. You can even lead them to an 3 (or 4 or 5) dimensional example.
What languages are these kids using? Since it’s a high school class, I fear it’s probably either C++ or JAVA. It’s unquestionably best to first introduce recursion using examples in a functional language, because the code is a lot simpler and the entire language is designed around making recursion useful. I was first introduced to recursion via Rex, during my second CS course in college.
The main problem with the object-oriented languages, as I see it, is that the kids may ask you for an example where recursion actually gives significantly better performance or more simplicity than iteration. Finding a simple example in C++ or JAVA could be difficult.
i would have to agree that the maze solver is the best way, when i learned about recursion, it didnt really make clear sense until i saw it from that perspective, dont forget to mention… that if it can be done iteratively it should be done iteratively… or some such…
Heh. I remember when I went from procedural to functional languages for the first time, and I was put off by the lack of good looping structures. I didn’t `trust’ recursion yet, but recursion is the only good way to implement an iterative process in most functional languages. I struggled with it, spending plenty of time writing junk code at an interactive prompt, and then a little switch flipped. I can now write recursive code almost as naturally as iterative, and the concept no longer frightens me.
Recursion is a great way to write elegant code, and I expect a lot of a-ha moments when individual students finally catch on.
(Teaching a functional language may be outside your purview, but a small Lisp or Scheme subset is simple to learn and it really hammers in the notion of a function as a first-class object, not just a collection of code. Looking at it one way, treating functions as first-class types is a good way towards run-time polymorphism. Looking at it from a more theoretical perspective, you can introduce Alonzo Church’s Lambda Calculus and, through that, the notion of effective computability.
Wrong. Firstly, programs are meant to be read by humans first and machines second. (Thank you, Donald Knuth.) Anything that increases code readability is fair game.
Secondly, any compiler worth its space in RAM knows how to optimize tail-recursion and similar constructs into efficient looping code.
I use recursion most often with traversing directories. This might be a good, simple example that the students can understand – they’re probably all familiar with the hierarchical nature of the file system. E.g.,
recursive_list(directory) {
for each file in directory {
print the file name
if it's a directory, recursive_list(directory)
}
}
You could also add code to do indentation, so the hierarchical structure is visible.
