Recursion and Russian nesting dolls

This post is the third of a series adapted from my conference talk, Fun, Friendly Computer Science.

Russian nesting dolls are a great metaphor for recursion. If you’ve never played with nesting dolls, they are exactly what they sound like. Each doll is the same except for its size and they each open and the doll inside is smaller and smaller until you get to the smallest child which does not open. When you reach the smallest child, you reverse the process, closing each doll one by one in reverse order.

Recursion has a reputation in computer science of being intimidating but what is it exactly? Recursion is the process by which a function calls itself directly or indirectly. The function that is calling itself is called the "recursive function” (if someone asks you that in an interview, it’s not a trick question 🤗).

If you continue calling the recursive function infinitely, you’ll cause a stack overflow exception. You have to set up a condition where the recursion exits the continued nesting and returns a finite value. This is called the base case. In our nesting doll example, the smallest doll that does not open is the base case.

This all sounds simple enough, but it can be really hard to write recursive code. And it can be even harder to hold a mental picture of what is happening within a recursive function. So let’s look at a code example.

count() { 
  return this.countNestedDolls(this.bigDoll); 
} 

countNestedDolls(doll) { 
  const child = doll.open(); 

  // base case
  if (!child) { 
    return 1; 
  } else { 
    return this.countNestedDolls(child) + 1; 
  } 
} 

In this example, count is indirectly recursive and countNestedDolls is the recursive function. So let’s walk through this code as if it was being executed not on a computer, but by a real person. Let’s say I hand you a nesting doll set and tell you to count them.

• You’re going to start with the largest doll (line 2).
• You are going to open it (line 6).
• It has a child. You’re going to do the same process with the child, remembering when you come back to close it that you’re going to add one for the largest doll that you opened (line 12).
• Now you open the second largest doll which also has a child inside. So you’ll repeat the process, remembering when you come back to close this doll that you’re going to add one.
• And so on, until you get to the smallest doll in the center. You try to open it, but it doesn’t open. There is no child. So you start the process of counting there, returning 1 (line 10).
• Then you come out of that function invocation to close its parent doll and remember that you have to add 1 when you close it, so you have 1 + 1 = 2.
• Then you come out of the next function invocation to close its parent and add 1, so you have 2 + 1 = 3.
• And so on, until you return the final sum of nesting dolls that were in the set.

If that was hard to follow written out, here’s a picture that might help. You continue to fall through each function invocation until you reach the base case, returning 1. Then you add 1 to the returned value as you move through each function invocation on the stack.

Recursion uses

Everything that you can do recursively, you can also do iteratively so you can think of recursion as fancy looping. Recursion shines in places where nesting feels logical and is easy to conceptualize. If you are a web developer, you may use recursion to render nested navigation menus or determine the path to render for the user’s breadcrumb.

Just because recursion is a traditional computer science strategy does not make it an inherently elegant solution. If there is no easy to understand nesting in the model you are trying to represent programmatically, then recursion is not the best use case. Make sure you aren’t contorting your code to fit “elegant solutions.” Instead, write your code to represent the real world models you’re working with. The next developer who touches your code will thank you 🤗