Analogy for teaching recursion

Question

When teaching recursion, what is the best analogy people use to teach the idea of recursion. There are some nice artistic representations

And the idea of repeatedly cutting a phone book or dictionary in half until you find a number/word (basically binary search). The only problem is students don't use phone books/paper dictionaries anymore and the artistic representation doesn't imply an end goal/state.

Answer 1

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.

Let's say you've already written your essay, and now you want to go back and perfect it. First you read the essay again, then you get feedback from others, then you make the changes, and then you revise the essay unless you consider your essay complete. In pseudocode:

function revise(essay) {
  read(essay);
  get_feedback_on(essay);
  apply_changes_to(essay);
  revise(essay) unless essay.complete?;
}

After the students understand the basics of what recursion is by following the simple example above or one like it, I'd move on to more sophisticated examples of recursion like a simple sort. Take merge sort for example (this assumes arrays have been taught):

function sort(array) {
  a = array.first_half;
  b = array.second_half;
  sort(a);
  sort(b);
  merge(a,b);
}

function merge(a,b) {
  final = [];
  a_counter = 0;
  b_counter = 0;
  while (final.length < a.length*2) {
    if a[a_counter] < b[b_counter] {
      final.push(a.shift);
      a_counter++;
    } else if (b[b_counter] < a[a_counter]) {
      final.push(b.shift);
      b_counter++;
    }
  }
  return final;
}

Answer 2

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:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk." (from Wikipedia)

To solve the n disk tower problem:

1. Solve the n-1 disk tower problem
2. Move the nth disk
3. Solve the n-1 disk tower problem again.

Solving the 1 disk problem is trivial.

I can imagine coding this as a nice on-screen or physical computing challenge.

Answer 3

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 already full theatre of other computer scientists (they're all there watching War Games again) you decide to recursively determine your row.

You ask the person in front. Trouble is they didn't check either. So again being lazy they ask the person in front of them. This continues until the bottom row is reached. This person knows they are in row 1 (they are there with a computer scientist friend but they aren't a computer scientist so they start counting at 1 not 0).

This is passed back to the person who asked, who being a computer scientist can add 1 to the number this person told them. This carries on until the original person asking finds out that the row in front of them is 31 and that must mean they are in 32.

He doesn't move though as he converts the value to hex to convince himself that it is row 20. He likes efficiency!

Cheo, C. (2015). 40 Key Computer Science Concepts Explained In Layman’s Terms. [Online] Available at: http://carlcheo.com/compsci

Answer 4

The image that I kept in my head when I was learning recursion was from Dr. Seuss:

Answer 5

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/con's of using both in implementation.

Flat-vs.-recursive formats rather than examples of recursion

Since any loop can be written in recursive format, there's basically infinitely many examples that could be presented. But, some seem to make more sense to people in recursive form than others. Why?

This could be a fruitful avenue for class discussion. For example, another answer here gave the example of fractals - why should fractals be seen as more recursive than, say, counting, when both loops can be written in flat form or recursive form just as easily? Then what does this imply - should we just always use one form over the other, or do they each have their place?

I love discussions like this, and I think that they could make the class fun!

Ideas for coursework (homework/projects):

1. [intro-level] Students are given a large number of loops in flat form, then must rewrite them in recursive form.

2. [intro-level] Students are given a large number of loops in recursive form, then must rewrite them in flat form.

3. [college-level] Short-answer questions about which form they should use in real-life coding scenarios. For example, in some situations flat form's much preferable to avoid stack overflows and implement tail-call optimization when not supported by the underlying platform.

4. [college/grad-level] Write an interpreter or meta-programming function that converts between flat and recursive forms.

Answer 6

I bought a set of nested Russian dolls (Matryoshka dolls).

1. Show the assembled set - how many dolls are there? We don't know, but maybe there is one inside - take a look

2. Yes, now how many dolls? We don't know, but maybe there is one inside...

3. Repeat until there is not a doll inside - this is the bottom of the stack.

4. Now reassemble the stack, counting the dolls as you go.

Answer 7

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 you want to know what the word "long" means. You look up the word in dictionary.com find that it means "having considerable linear extent in space." Lets say for the sake of example that you do not know what "linear" and "extent" means. Then you would look up those words definitions. If theres any word in those definitions that you don't know, you would look that up in the dictionary and so on.

In code, it'll look something like this:

public static void lookupInDictionary(String word){
   String definition = getDefinition(word);
   if(understandsAllWordsIn(definition)){
       return;
   } else {
       for(String word: wordsNotUnderstood(definition)){
           lookupInDictionary(word);
       }
   }
}

You can also use this to teach infinite recursion. Lets say this was the dictionary:

Hello: Hi
Hi: Hello

If one tried to call lookupInDictionary("Hello") or lookupInDictionary("Hi"), it would recurse infinitely.

Answer 8

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 in a programming course! Usually, you'll very early on cover order of operations and expression evaluation in a programming course--but the algorithm we teach them is recursive "find the innermost expression, evaluate it, then move outwards". Here's an example of it in use: http://courses.cs.washington.edu/courses/cse143/16au/lectures/power-of-recursion/lecture12-recursion.pdf

Answer 9

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 masochism, to write and especially to prove. Take the Towers of Hanoi problem. When one sees how the problem just cleaves and dissolves into the recursive formulation, that experience of awe will drive one to a deeper and more nuanced exploration of recursion. Elegant expression requires no analogy.

Answer 10

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

Answer 11

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 applied over and over again to a problem until a base case is reached (such as a lack of resources or a height limit at which point water can't be delivered to the leaves)

Answer 12

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, the student looks at the other eight squares and repeats the process in each of them. And so on. And so on. That illustrates the process. If you do this in a program, you get the window below. And here's a Java program I wrote to create that window: Squares.java.

Answer 13

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 block itself. With each new call, I "pushed" the function call onto my stack and then "popped" them off one by one as the functions began to return values rather than more function calls.

I used a basic factorial problem, so my stack of blocks ended up looking something like this:

--factorial(1)--
--factorial(2)--
--factorial(3)--
--factorial(4)--
--   main()   -- 

Students could see how one call to factorial relied on other calls and so on until reaching the base case which "tore down" the stack we had just built.

One of the magical elements of recursion for students is how a function can call itself. The idea of return values and a growing stack of function calls at least gave a tangible and visual example for something that can be abstract and initially challenging to understand.

Answer 14

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 interesting because it's either interesting or if not interesting is the first non-interesting number and therefore interesting. $$F(F(F(0)))$$ is interesting because...

Answer 15

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 green bag and the tent. You know what the tent weighs. You know that the green bag holds the red bag and the brown bag. Etc.

Similar problems include the "salary burden" of a VP who has several departments under them, and each department has a department head with teams under them, and so on, but without a strict hierarchy so some departments have no teams, just everyone reporting to the head, and some people report directly to the VP but don't head a department, etc. You could also do revenue within a large company the same way. Or inventorying your personal possessions.

Answer 16

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 dissertation studies. Your advisor has given you a topic to explore, but you know little about it in detail. The advisor suggests a research article as a place to start. The process is:

If the article is by Euclid, read it and you are done.

However, if it isn't by Euclid, then after you read it you will not likely understand everything, so (recursively) read all of the articles in that article's bibliography. However, if you do understand everything already, there is no need to pursue the bibliography.

This process (read and chase bib) proceeds until you understand everything you've read or until you reach Euclid.

---

This process is actually closer to the truth than you might expect, but it has at least one (maybe two) serious flaw. After describing the process to students (even relative beginners), ask for their help in identifying the flaw(s). This can lead to a deeper understanding of recursion than a simple (flawless) example.

Answer 17

Google recursion.

It's a recursive link! Ah, google easter eggs...

Then, you can maybe give them a problem that depends on recursion - like, say, a multiplication algorithm of some sort (I saw one somewhere that used recursion and was pretty simple - I'll edit to add it if I find it) to give a more programming oriented example.

Answer 18

I hesitated to answer since most of the answers given are already so good. However, I've also used https://en.wikipedia.org/wiki/There_Was_an_Old_Lady_Who_Swallowed_a_Fly as an introduction, though it isn't precisely recursive. It is more focused on a list as a stack, which leads naturally to recursion.

In my class we occasionally had "Choir Practice" in which I'd ask a number of students to participate in various "games." For this exercise I'd give each of them a Script card. Starting with only myself and one student, I'd do one verse of the poem, then "push" another student on to the stack and continue.

I start (with one student) and say:

There was an old woman who swallowed a fly,

I then point to the one student who reads his/her script card. The first says:

I don't know why she swallowed a fly, Perhaps she'll die.(Take a bow.)

Then, "pushing" the second student (now I have a stack of two), I'd say:

There was an old woman who swallowed a spider, That wriggled and jiggled and tickled inside her,

I'd point to the (new) stack top who would read the script:

She swallowed the spider to catch the fly, (point to the next person)

etc for as long as you like. "Pointing" to a person is passing them the message to read (sing-act) their own script.

Depending on how you talk about the exercise you can use it to reinforce lists, stacks and/or recursion. Note the base case (...take a bow). The "message" sent is recursive, though. You can also explore what happens without a base case in your follow up discussion.

A bit foolish, but my University students tended to like it even if they did roll their eyes a bit.

Note that such "active learning" exercises always require follow up discussion in which you point to the mapping between the elements of the game and the lesson to be learned and students get to unwind any puzzlement.

---

Here is a link to the card deck

Answer 19

When I was first taught recursion in a high school CS class, the teacher had us read a short story called Martin and the Dragon, found in chapter 8 of "Common LISP: A Gentle Introduction to Symbolic Computation" by David S. Touretsky. In the story, a boy named Martin visits an unruly dragon and uses recursive techniques to coerce it into helping him with a few different computational tasks that are common in LISP, including iterating over a list, calculating a factorial, counting, and calculating fibonacci numbers (which also teaches infinite recursion).

A shorter analogy might be a multi-level marketing scheme - it starts with one person, who has to recruit several more, who each in turn have to convert a few others, and so on.

Genealogical lines are also a naturally recursive data structure - you have two biological parents, who in turn each have two biological parents, and so on and so forth. It can also work for children and/or other species.

Answer 20

This is an old question with lots of answers, but a new one just occurred to me: long division. The benefit here is that most students will already be familiar (and hopefully comfortable) with the mechanics of it, so "recursion" is just another way to talk about something that's already familiar.

Answer 21

L-system trees are a fun, clear, simple way to show recursion.

e.g.: http://www.malsys.cz/Gallery/GetThumbnail/JFI1IzqW/IqdVGQ

I've taught this in beginner-level Python lessons, and it only requires a few lines of code to build complete trees. Most students love the artistic outcome - especially that so little code produced so much graphics.

Answer 22

A new answer for this came to me today. Infinite indirect recursion:

Pete and Repete are in a tree. Pete falls out. Who's left?

Answer 23

Came across this one. I simply loved it:

Hofstadter's Law: It always takes longer than you expect, even when you take into account Hofstadter's Law.

This is especially good when explaining debugging a recursive method, or the call stack. When you reach the end of the sentence, you go to the definition of Hofstadter's Law (If you are a compiler). And this goes on and on (essentially a stack overflow).

Answer 24

You're working in an office. If a question comes up, the first person you consult is yourself. If the person to consult doesn't know the answer, they consult their manager, and upon receiving the answer pass it down the hierarchy again. Recurse until you have the answer.

So:

ask( person from, person to ):
  if not: from knows the answer
     ask( from's manager, from )
  tell( from, to )

and invoke this with

ask(me,me)

(You still have to define tell(from,to) and make sure that's a no-op if from==to.)

I like this example because it is not trivially iteratable as tail recursion. This explicitly goes up and down the stack.

Next step: if you ask something of someone, you take out a notepad to record what they tell you. If that person doesn't know, they take out a notepad and ask further. Now you know where stack overflow comes from: there is a bunch of notepads open simultaneously, and they all take up some amount of memory.

Answer 25

I thought of repetitive song lyrics, initially the Song That Never Ends - a good example of infinite recursion. Then came to mind Ten Green Bottles, which I think is a nice simple illustration with a clear base case and inputs that keep reducing, ultimately to the base case.

Answer 26

You can do some stuff with the filesystem
like. start with a folder and count all files in it
or let them create a overview of folders and files

Answer 27

Pretty late to see this. Thought to add my two cents as well.

Recursion simply reminds me of the barber shop (provided he has parallel mirrors on either side of you) where we used to observe the array of mirrors (Fun Fact: once even counted them uptil 83 until they were no more visible). Also, during matches, when often cameraman used to pan at the giant-screen and we used to see the array of screens in it (all recursively).

Answer 28

I think there are two separate aspects to understanding recursion:

1. How to use recursion to solve problems
2. How recursion is evaluated

How to use recursion

Let's look at an example: maximum depth of a binary tree (where a tree with a single node is depth 1). A recursive solution in python might look like this:

def max_depth(root):
  if root is None:
    return 0

  return 1 + max(max_depth(root.left), max_depth(root.right))

You don't need to think about how this is actually evaluated; you just define it how you would mathematically. If I somehow know that the maximum depth of the left branch is $x$ and the maximum depth of the right branch is $y$ and that $x > y$ (without loss of generality), then I know that the maximum depth of the entire tree is $1 + x$. This way of thinking about problems is one way you can use recursion.

Of course, you need to make sure that the inputs to the recursive calls are in some way smaller than the input to the function that makes the recursive call, which segues into how recursion is evaluated.

How recursion is evaluated

To think about how recursion is evaluated, we can use the same example. In the example above, there are pending recursive calls, waiting to return (note that recursion does not necessarily have this, see tail call). To see this, suppose our tree looks like this

    O <- root
   / \
  O   O
 / \
O   O

and you have a variable r storing the root. If you call max_depth(r), it will try to evaluate the else clause; it will evaluate max(max_depth(r.left), ...) and then add 1 to that result. To the r.left recursive call, the input looks like this

     O
    / \
   O   O

And for the r.right recursive call, it is simply this:

O

The r.left recursive call evaluates else clause, which means it tries to evaluate the max depth of the left and right subtrees, and add 1 to whichever is greater.

The r.right recursive call also evaluates the else clause.

So at this point you think of the return value of the original call to max_depth looking like this:

return 1 + max(
               1 + max(max_depth(root.left.left), max_depth(root.left.right),
               1 + max(max_depth(root.right.left), max_depth(root.right.right))
              )

Both recursive calls of the left branch have trees that look like this now

O

while both recursive calls of the right branch, since it was just a node without any children, have trees that are empty, which is None in Python. Thus, they fall to the base-case, which means it is evaluated as 0.

So now the original return value is like this

return 1 + max(
               1 + max(
                       1 + max(max_depth(root.left.left.left), max_depth(root.left.left.right)),
                       1 + max(max_depth(root.left.right.left), max_depth(root.left.right.right))
                      ),
               1 + max(
                       0,
                       0
                      )
              )

All recursive paths from the right branch already reached the base-case, and now on this recursive call, all children of the left branch will as well, which means the return value of the original function is now

return 1 + max(
               1 + max(
                       1 + max(
                               0,
                               0
                              ),
                       1 + max(
                               0,
                               0)
                      ),
               1 + max(
                       0,
                       0
                      )
              )

which evaluates to

return 1 + max(
               1 + max(
                       1 + 0,
                       1 + 0
                      ),
               1 + 0
              )

and

return 1 + max(
               1 + 1,
               1 + 0
              )

and

return 1 + 2

finally

3

Note, this evaluation was not performed according to any formal evaluation model (see substitution model or environment model); it was merely to help build intuition for how evaluation could be done.

Extra (tail-recursion): I mentioned earlier about how recursion does not necessarily have these pending function calls that must be recursed back to once they finally have the result of the recursive call. Consider a recursive function to find the sum of a list (ignoring the python built-in sum()):

def sum_list(lst):
  if lst == []:
    return 0

  return lst[0] + sum_list(lst[1:])

This indeed would have pending recursive calls, as it waits to add lst[0] to the result of the recursive calls. We can make this tail-recursive by accumulating the sum of the list in an argument that is simply returned unmodified at the end:

def sum_list_tail_recursive(lst, result):
  if lst == []:
    return result

  return sum_list_tail_recursive(lst[1:], result + lst[0])

Once this evaluation reaches the base-case, it has the the result of the original call to sum_list(), and it does not need to be added to, or modified in any way as you recurse back up, and so if a compiler/interpreter recognizes this, it can optimize by skipping directly to the first call, eliminating the need to recurse back to it step-by-step.

Answer 29

Here is my cake-baking analogy:

Suppose the recipe for a 3-layer cake said "first bake a 2 layer cake, then add flour, sugar, and butter, and put it in the oven".

And the recipe for the 2-layer cake says "first bake a 1 layer cake, then add flour, sugar, and butter, and put it in the oven".

But once you get to the 1-layer cake, that's it. You've reached the base case. The buck stops there. Unlike the recipes for the 2-or-more-layers cakes, the recipe for the 1-layer cake doesn't refer to any other recipes.

I think this analogy captures the concept of the base case (the 1-layer cake) and the recursive step (add sugar, flour, and butter then bake).

Answer 30

I came up with an analogy that helped me visualize recursive programming a great deal.

1. Imagine a water tank with an inflow pipe on one side. On the other side, about halfway up the tank, is the outflow pipe which is where you collect the water.
2. Water enters the inflow pipe. As it enters, it gets tested to see if it's clean. If it's found to be clean, a valve will empty the water directly into the tank and let the clean water flow into the tank and then right through to the outflow pipe and we are done.
3. But if the water test reveals that it is dirty, it gets decontaminated by some amount then gets directed into another tank inside of bigger tank.
4. This second tank does exactly the same thing as the outer tank. It first tests the water, dumps it into the tank if it is clean and if it isn't, it cleans it a little bit, and then sends it to a third inner tank. This process continues.
5. When the last inner tank is reached and the water is completely clean, the valve lets the water spill directly into the tank. This water then flows out of the tank though the outflow and into the outer tank surrounding it. That outer tank fills up until water spills out into its outer tank. Each of these tanks can also treat the water if they want (add chlorine or fluoride to it or even send it to another recursive processing tank).
6. This cascading action continues until the last outer tank spills out the clean, processed water, representing the data we desire.