What are some games involving recursion?

Question

I need to introduce a group of 5-15 people to recursion and I would like to do so by using a physical game/dance/activity they can play to get a feeling for recursion. The class is not so much focused on CS than general concepts so anything computer or programming related is out (but programmers are still the best people I could think of to bombard with such as question).

I was thinking about using some kind of clap game such as teenie girls like to play that includes recursion but couldn't come up with one yet. The game/dance might well be ridiculous, it should just be interactive and get them some intuitive feeling for what recursion is and how omnipresent it is in our surroundings.

Looking forward to your suggestions!

Answer 1

A real world example of recursion could be build around Towers of Hanoi:

A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. The following procedure demonstrates this approach.

• label the pegs A, B, C—these labels may move at different steps
• let n be the total number of discs
• number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg C:

• move n−1 discs from A to B. This leaves disc n alone on peg A
• move disc n from A to C
• move n−1 discs from B to C so they sit on disc n

The obvious way would be to explain recursion with the physical game. There are quite a few instances where the game has been used educationally, some are discussed in this paper¹:

In this context, the Tower of Hanoi can be seen as helping students progress from “words, pictures, or diagrams” to more “standard conventional...notation.” Students bring to the puzzle their existing knowledge of mathematics, of order, rules, games and concrete manipulation. They then use these to engage with the Tower of Hanoi in concrete and enactive terms. Guided by a tally of their moves and by feedback on the lowest possible number of moves, these predominantly concrete operations can be seen as leading the student to more “conventional,” “formalized,” and “symbolic” understandings. Students in this sense are able to build progressively on “informal ideas in a gradual but structured manner”

Towers of Hanoi and Matryoshka dolls are presented as suitable for teaching recursion in a paper aptly titled "Recursion: From Drama to Program". Unfortunately it's behind a registration wall.

As mouviciel wrote in a comment, a dance game is fairly simple:

I imagine a stage with three special places where dancers are placed one behind the other in such a way that public always show all heads. The narrator want to hug the taller one but dancers can only stay in one of the three places and public must always see all heads.

A team at Sapientia University has released quite a few algorithm dance videos:

• Quickshort
• Merge sort
• Shellsort
• Insertion sort

Simplified versions of those could be perfect for what you are looking for. For further inspiration, take a look at this Stack Overflow question, on real world examples of recursion.

_{¹ Warning, PDF.}

Answer 2

How about applying quicksort on your group of friends to sort them according to height? Or mergesort will probably be simpler to understand.

Answer 3

Well, I suppose fractals and their occurrence in nature are a good starting point to show recursion:

• Let them draw a Sierpinski triangle
• Show them snowflakes or ferns and other naturally occurring fractal structures
• Show them actual fractals, that resemble to nature
• And why not a fractal that doesn't necessarily resemble to nature, but is evidently very complex and beautiful, to illustrate how a simple recursive rule can yield such a thing.

If you find a handy way to do it, generate a landscape with them, using the Diamond-square algorithm. This can be basically done with anything suitable for use as building blocks placed on a grid.
If the blocks are big enough, you can easily distribute the work and parallelize it :D

Also, you can maybe look at how humans actually use this principles themselves when building hierarchies, where recursively a member of each layer controls a group of people from the next level and so on.

Lastly, Achilles and the Tortoise are a great example of (tail) recursion, although it might at the same time seem a little discouraging.

Answer 4

Songs like "99 bottles of beer on the wall" are sort of recursive, or games where each person has to add an item to a list, then recite the whole list.

Answer 5

I think recursion is something one gets in an aha-moment; the time it takes to truly understand it varies considerably between individuals. Therefore, I don't think it is something one learns in a group.

I suggest that you explain the principle and let everyone solve a puzzle on their own. Tower of Hanoi is fine, but lacks realism (unless you can get really heavy disks so that it is physically impossible to lift more than one at a time). I'd personally recommend this hoop puzzle as it is initially hard to solve, but becomes surprisingly simple once one understands recursion.

Answer 6

Can you think on having a calculator type of thing, where 10 people go as a group to a person(calculator) and the calculator using recursion (going to the same function again) tries to subtract (for that matter use division) 2 people from the group? initially 10 people visit the calculator --calculator returns 8 then 8 people visit the calculator --calculator returns 6 and so on....

I hope my suggestion was of some help

Answer 7

Musical chairs. Each recursion removes the slowest player.

Also gets people activated which is a plus, gets blood flowing and increases alertness :)

Answer 8

Sing the 12 Days of Christmas.

Or the grocery store game.

• "My name is Alice and I bought a tomato."
• "My name is Bob and I bought an orange. Her name is Alice and she bought a tomato."
• "My name is Charlie and I bought an apple. His name is Bob and he bought an orange. Her name is Alice and she bought a tomato."

So you can teach them about stack depth. It is self referential and illustrates depth.

Edit: Actually, maybe a fire brigade would work. Line the kids up and give someone on the end a bucket and someone on the other end a load (balls, blocks, toys) to fill the bucket with. Have the kids pass the bucket all the way to the end, put something in it, then pass it back. That would illustrate how indirect the request is. Even though the first kid wanted the toy, he had to wade through all these intermediary kids to get his prize.

Answer 9

As an artist and a programmer I look to identify three principle aspects when I am observing recursion or considering the concept in use,

1. identify a rule which has self-reference (in programming an example is a named function containing the same named function),

2. producing a process of repetition with the requirement of a break case (to stop looping forever),

3. resulting in observable self-similar patterns.

The last rule will not be observable feature of the results of a program--you will not see the pattern but have the knowledge the same rule was applied multiple times. The beauty of recursion in programming is "observed" in the economical code. The reverse is the case in biological growth and natural ecological patterns where we observe number three and infer one (and maybe two).

Standing on the shoulders of giants, I hope I am correct in suggesting these three elements are, in these two combinations, required to distinguish recursion from iteration. If your project can teach students to make this distinction they will have learned recursion.

---

Its with this in mind my suggestion for teaching recursion is to observe nature. A most excellent primer on observing recursion is the Nova program Hunting the Hidden Dimension (and for the time being can be viewed at Youtube). I wish to point out this passage from the video describing recursion in trees:

5:15 "One of the most familiar examples of self similarity is a tree. If we look at each of the nodes, the branching nodes of this tree, what you will actually see is that the pattern of branching is very similar throughout the tree."

What is more amazing is different trees have different patterns. The count of tree limbs from one compass point, twisting upward to the next tree limb at the same compass point with be a specific number. This makes for an interesting nature walk with so many points of observation from the trunk to the tips of the branches. The tree is the best example, but of course recursion doesn't stop there.

Going one step further, if you were teaching art, this knowledge is very useful in mapping what your mind says you're seeing to the true physical reality. This is because of the optical illusion of foreshortening when drawing objects which are arranged pointing toward the artist. Knowledge of recursion helps the artist understand what they are seeing when a branch is see from different angles. Again from the Nova episode, Mandelbrot said "think not of what you see, but what it took to produce what you see." Your natural drawings will be better because of it.