- 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.