Compare recursion to painting the layers of a Russian nesting doll to help students understand the concept.

  • A Russian nesting doll is a sequence of similar (except for the size) dolls inside of each other that can be opened. Each time you open a doll, a smaller version of the doll will be inside and you repeat the process until you reach the final doll, which will often contain a prize (like a piece of candy).
  • A recursive function is like a Russian doll. Ask students the question, "How do you paint the layers of a Russian doll?" Explain that if the doll cannot be divided, you should paint it (this is the base case). If it can be divided, then paint the inner doll and paint both halves of the current doll. When the doll can no longer be divided, you have reached the base case. 
  • Explain to students how the action of using the same method for painting the layers of a Russian doll is a recursive algorithm. Often Russian dolls are used as an example of recursion; however, the doll is only a recursive object not a recursive algorithm. This makes the act of painting the doll a much stronger analogy.

More about this tip

External Source

From: WOOLLARD, WILLIAM JOHN (2004), “The rôle of metaphor in the teaching of computing; towards a taxonomy of pedagogic content knowledge.”, University of Southhampton, School of Education, PhD Thesis, pg 128

"Non-Programming Resources for an Introduction to CS" by Joseph Bergin, Myles McNally, Mike Goldweber, Charles Kelemen, Tom Naps, Chris Power, and Stephen Hartley.