102
votes
What are good examples that actually motivate the study of recursion?
I find a very easy to understand example for recursion is the folder structure on a computer.
Look through all folders (within a certain location) and... list all .doc files, for example.
First, you ...
- 981
30
votes
Analogy for teaching recursion
The Tower of Hanoi was one of the first ways that I encountered recursion.
"The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
Only one disk ...
- 1,256
26
votes
What are good examples that actually motivate the study of recursion?
One good example is to make permutations of all of the letters in a word of arbitrary length. It's quite tricky to do iteratively, since you essentially have to recreate the program stack to get it ...
- 32.9k
21
votes
What are good examples that actually motivate the study of recursion?
Writing recursive code to output the Snowflake Curve (Koch snowflake) was something that definitely pushed my buttons early on.
It's formed as follows:
The Koch snowflake can be constructed by ...
- 311
20
votes
Accepted
How to respond when students ask "is recursion good practice"?
Quite honestly, I would be upfront with them about the debate. Send them to a couple other SE threads:
Efficiency: recursion vs loop
“Necessary” Uses of Recursion in Imperative Languages
Are ...
- 9,082
20
votes
Analogy for teaching recursion
Can't claim it's my own idea but I can embellish it a little...
Imagine you are entering a cinema. You sit down in a row but realise you had to sit in row 20. Being a lazy computer scientist in an ...
- 241
20
votes
What are good examples that actually motivate the study of recursion?
Other than the obvious merge sort, I really like the minimax algorithm, especially when applied to creating a computer player of a simple game.
Start with something simple like tic-tac-toe. When it's ...
- 5,430
16
votes
Analogy for teaching recursion
The image that I kept in my head when I was learning recursion was from Dr. Seuss:
15
votes
Accepted
Analogy for teaching recursion
I like to use something that a student can connect with and something that they have to deal with regularly. You could choose any recursive everyday activity, but I like to choose revising an essay.
...
- 4,795
15
votes
How to respond when students ask "is recursion good practice"?
When I teach recursion, even if I am not at a point in the curriculum where it is possible to introduce trees in coding problems, I always at least provide a high level discussion of trees, and the ...
- 271
13
votes
What are good examples that actually motivate the study of recursion?
I'm going to focus on student's understanding recursion at a fairly deep level, rather than coding.
First, to really understand recursion you need a sense of its parts. There is the base case, of ...
- 36k
9
votes
Analogy for teaching recursion
Recursion as a loop
I'd present recursion as a form of a loop rather than being separate thing. Then, I'd show the students how to covert between flat form and recursive form, and discuss the pro's/...
- 897
8
votes
Analogy for teaching recursion
Although there already is many great answers, one analog I found helpful was the dictionary lookup analogy (this is different than the dictionary binary search analogy). It goes like this:
Lets say ...
- 81
8
votes
Analogy for teaching recursion
I bought a set of nested Russian dolls (Matryoshka dolls).
Show the assembled set - how many dolls are there? We don't know, but maybe there is one inside - take a look
Yes, now how many dolls? We ...
- 321
8
votes
What are good examples that actually motivate the study of recursion?
Tree Traversal
Let's compare the recursive and iterative approaches to doing an in-order traversal of a binary search tree.
Recursive approach
...
- 519
8
votes
What are good examples that actually motivate the study of recursion?
Operating on the key word, motivate, I do believe that Andrew T. had the best choice with Tower of Hanoi. Yes, it's an old one, and it does not lead to anything useful once it's done, (the code is not ...
- 5,435
7
votes
Analogy for teaching recursion
Rather than use analogy, I think it best to demonstrate the power of recursion on a problem for which the recursive solution is natural and the alternative solutions are an obvious exercise in ...
- 510
7
votes
Analogy for teaching recursion
One of my favorite examples of recursion is evaluating an arithmetic expression. The downside is that evaluation isn't particularly interesting, but the upside is significant: they've already done it ...
- 215
7
votes
Analogy for teaching recursion
I've used Carl Burch's analogy several times
Somebody is a Jew if she is Abraham's wife Sarah, or if his or her mother is a Jew.
He has a nice set of pages at CMU
- 71
6
votes
Analogy for teaching recursion
I demonstrated this recursion example in class. I draw a large square on the board and ask a student to picture it like a 3x3 grid (like Tic-Tac-Toe). Then the student outlines the center square. Next,...
- 1,044
6
votes
Analogy for teaching recursion
Rather than use an analogy, you could give a real world example. The way a tree grows, the shell of a snail, the petals on a sunflower. I believe these are all fine examples - the same solution ...
- 77
6
votes
What are good examples that actually motivate the study of recursion?
Several answers have said things like "We need recursion to handle tree structures." The problem with this type of answer is that the student then asks "Why would we have a tree structure in the first ...
- 241
5
votes
Analogy for teaching recursion
To make for a hands-on demonstration, I brought in a set of my son's Mega Bloks:
I slowly built up a stack of blocks, and using a dry-erase marker, wrote the calling function and its argument on the ...
- 9,082
4
votes
Analogy for teaching recursion
My first practical use of recursion was to work out the total weight of a bunch of containers (portage packs and the various stuff sacks and whatnot inside them.) You know that the blue bag holds the ...
- 181
4
votes
Analogy for teaching recursion
I think a computational joke is in order to help students get started.
All numbers are interesting, for a function $F()$
$F(0)$ is interesting because it's the first number.
$F(F(0))$ i.e. 1 is ...
4
votes
Analogy for teaching recursion
A fairly deep example of a recursive process that has some serious issues that might be discussed with students is as follows.
Suppose that you are a doctoral student in mathematics beginning your ...
- 36k
4
votes
How to respond when students ask "is recursion good practice"?
Having a discussion about the plusses and minuses can be valuable, but sometimes what you need is a motivating example. It's true that loops and recursion are equivalent in the sense that they can ...
- 32.9k
4
votes
How to respond when students ask "is recursion good practice"?
In addition to the other good answers already provided, I want to add that students should learn recursion because they will encounter it in real life.
Any one of them who goes on to program for a ...
4
votes
How to respond when students ask "is recursion good practice"?
For any language/compiler that supports tail-call optimisation, there is no use of the stack for recursion. So you can implement while True: recursively. In these ...
- 10.7k
4
votes
How to respond when students ask "is recursion good practice"?
An introductory programming class is a good place to familiarize students with some real-world issues in programming apart from the more popular ones. Using recursion is just one example of how they ...
- 141
Only top scored, non community-wiki answers of a minimum length are eligible