7. Recursion

Written by Jonathan Sande

You probably heard this joke in third grade:

• Pete and Repeat were in a boat. Pete fell out. Who’s left?
• Repeat.
• Pete and Repeat were in a boat. Pete fell out. Who’s left?
• Repeat.

… and on it went until someone got tired.

This is an example of an infinite loop. A related term is recursion, describing something that “occurs again.”

In language, a recursive definition points back to itself. For example, programmers have taken a particular liking to recursive acronyms:

• YAML: YAML Ain’t Markup Language.
• GNU: GNU’s Not Unix!
• gRPC: gRPC Remote Procedure Calls.

There are also recursive patterns in nature. For example, a tree has branches, which divide into smaller branches, which divide into still smaller branches. River systems and blood vessels also show this tree-like branching pattern into ever-smaller parts.

Computing has borrowed the tree metaphor, and in this chapter, you’ll learn how the technique called recursion can be a powerful tool to help you visit all the nodes of a tree-like data structure.

Recursion in Computing

In programming, recursion is when a function calls itself. Here’s an example:

void tellJoke() {
  print("Pete and Repeat were in a boat. Pete fell out. Who's left?");
  print('Repeat');
  tellJoke();
}

tellJoke calls itself from inside the function. And because there’s nothing to stop it, it’ll continue to do so seemingly forever. This is known as infinite recursion.

Run that code from main like so:

void main() {
  tellJoke();
}

Rather than continuing forever, though, the program will soon stop with the following error:

Unhandled exception:
Stack Overflow

Stack Overflow? Isn’t that the name of that website?

Yes, that’s where the site got its name. The real question is: If you ask a question about a stack overflow on Stack Overflow, is that recursion? Or maybe reading a chapter about stack overflows that asks you about asking stack overflow questions on Stack Overflow is. Or if you ask your friend … never mind — that could go on forever, or at least until your mind overflows.

You’ll come back to the stack overflow error later in the chapter.

Recursion vs Iteration

Rewrite the previous joke as a loop:

void tellJoke() {
  while (true) {
    print("Pete and Repeat were in a boat. Pete fell out. Who's left?");
    print('Repeat');
  }
}

You don’t need to bother running that infinite loop. It won’t crash. It’ll just lock up your computer.

Another word to describe looping is iteration. Recursion and iteration are two different means of repeating a task. You can write any recursive function as an iterative function and any iterative function as a recursive function.

The Base Case

Infinite loops and infinite recursion aren’t very useful by themselves. That’s why you use for loops and why while loops typically have a test case or a means of breaking out of the loop:

int i = 0;
while (true) {
  print('Knock knock');
  print("Who's there?");
  if (i == 5) break;
  print('Banana');
  print('Banana who?');
  i++;
}
print('Orange');
print('Orange who?');
print("Orange you glad I didn't say banana again?");

The loop above breaks out of the iteration on the sixth loop.

Like iteration, recursive functions also need a way to know when to stop calling themselves. This signal to stop is known as the base case.

To see this in action, write a recursive function that counts to 10 and then stops:

void countToTenRecursively([int i = 1]) {
  // 1
  if (i > 10) return;
  print('$i Mississippi');
  // 2
  countToTenRecursively(i + 1);
}

Here are some notes on the numbered comments:

1. Base case: If i is greater than 10, the function will immediately return. This will prevent the function from calling itself anymore.
2. Recursive case: The function calls itself with one higher value for i than the last call was. i defaults to 1 in the beginning, but on the second time through, it’s 2, then 3 and so on through 10.

Note: In case you weren’t one of them, some school children use “Mississippi” when counting seconds in games like Hide and Seek. Modify the code above with async and await Future.delayed(Duration(seconds: 1)) to make it more realistic if you prefer.

Exercises

Solve the following exercises both iteratively and recursively:

1. Count by fives to 100. (5, 10, 15, …, 100)
2. Print all the square integers from 1 to 100. (1, 4, 9, 16, …, 100)

When Recursion Is Useful

Although you can solve certain problems both recursively and iteratively, sometimes one way makes more sense. The following problem will show that.

Encountering a Tree-Like Data Structure

Say a particular rabbit has three baby rabbits, and each of those bunnies grows up to have its own babies. The image below shows their family tree:

In code, define your Rabbit class like so:

class Rabbit {
  Rabbit(this.name, {this.babies});
  final String name;
  final List<Rabbit>? babies;
}

Then, build the family tree from the previous image like this:

final family = Rabbit(
  'Mommy',
  babies: [
    Rabbit(
      'Hoppy',
      babies: [
        Rabbit('Bunny'),
        Rabbit('Honey'),
        Rabbit('Sunny'),
      ],
    ),
    Rabbit(
      'Moppy',
      babies: [
        Rabbit('Doozy'),
        Rabbit('Woozy'),
      ],
    ),
    Rabbit(
      'Floppy',
      babies: [
        Rabbit('Nosey'),
        Rabbit('Mosey'),
        Rabbit('Toesy'),
        Rabbit('Rosey'),
      ],
    ),
  ],
);

Now, if you wanted to print the name of each rabbit in the family, how would you do it? Could you do it with a loop? Take a minute to think about it.

Visiting the Members

If you have a linear collection like a list, queue or any other data structure you’ve studied thus far in the book, it’s relatively simple to loop over the members. But when you have a branching data structure like the rabbit family tree, it’s not so easy to visit each member using a loop.

Recursion comes to the rescue, though!

Write the following recursive function:

void printName(Rabbit rabbit) {
  // 1
  print(rabbit.name);
  // 2
  final babies = rabbit.babies;
  if (babies == null) return;
  // 3
  for (final baby in babies) {
    printName(baby);
  }
}

Here’s what’s happening in the numbered comments:

1. You start by printing the given rabbit’s name. This is the main task you want to accomplish for each rabbit.
2. This is the base case. If a rabbit has no babies, you don’t need to continue.
3. Call printName for each baby a rabbit has. This is the recursive case. After reaching the end of the for loop, you stop recursing. This is a second base case.

Add the following line at the bottom of your main function:

printName(family);

family here is Mommy rabbit with all the babies and grandbabies.

Run that to see the result:

Mommy
Hoppy
Bunny
Honey
Sunny
Floppy
Doozy
Woozy
Moppy
Nosey
Mosey
Toesy
Rosey

Carefully observe the order. It might help to refer back to the image.

• You started with Mommy rabbit.
• Next, you took the first baby, named Hoppy.
• Then, before taking any of the sibling bunnies (Floppy or Moppy), you took the first baby of Hoppy. That bunny (named Bunny, coincidentally) didn’t have any babies, so you met the base case. Then, you took Hoppy’s next baby, which was Honey, the sibling of Bunny. Honey also had no babies, so you went on to Sunny.
• That was all of Hoppy’s babies, so you met another base case. But you continue to recurse over Mommy’s other babies by going on to Floppy and its babies.
• And so it continues until you visit all of the rabbits.

Using a Debugger to Observe Program Flow

To get a feel for how recursion works, it’s important to take the time to step over the logic in the same way the program does it. The debugger is useful for this.

Add a breakpoint in front of printName(family);.

Then, rerun your program in debug mode.

In VS Code, press the Step Into button repeatedly for each line:

Now, watch the logic play out:

• Note when you reach the base case.
• Note when the for loop finishes and you complete the function normally.

Now, repeat the procedure, but this time pay attention to the Call Stack window in the Run and Debug panel in VS Code. Note how when you go deeper into a recursive function, another printName is added to the call stack:

This is key to how recursion works, which you’ll read about in the next section.

How Recursion Works

In Chapter 4, “Stacks”, you learned about the stack data structure. Well, Dart uses this data structure internally to implement recursion. This internal stack is known as the call stack. When one function calls another, Dart pushes the new function onto the call stack. Each function on the stack is known as a stack frame.

When a function completes, Dart pops it off the top of the call stack. Because Dart saves the function states in the stack frames, the previous function continues from where it had left off.

The images in the following section will show how Dart pushes and pops functions to and from the call stack.

Visualizing the Call Stack

At first, the call stack is empty:

When you run your program, you start with the main function, so Dart pushes main to the call stack:

When you enter printName the first time, Dart pushes it to the stack. Because Mommy is at the top of family, this is Mommy’s stack frame:

Mommy’s first baby is Hoppy, so as you recursively call printName for each baby, Hoppy is first. Dart adds printName for Hoppy to the call stack:

Hoppy also has babies, so the recursion continues. You call printName for Hoppy’s first baby, Bunny, and Dart adds this function to the stack:

Bunny has no babies, so you’ve reached the base case. You exit Bunny’s printName function, so Dart pops it off the stack. Now, you’re back inside the Hoppy printName function:

The stack frame stored the execution state of Hoppy’s printName function, so you continue from where you had left off because you were looping through all of Hoppy’s babies. The next one after Bunny is Honey. You call Honey’s printName function, and Dart pushes it to the call stack:

Honey doesn’t have any babies either, so Dart pops its stack frame off the call stack:

Back in Hoppy’s printName function, you’ve now iterated to the last baby, Sunny. Call its printName, and Dart pushes it to the call stack:

Sunny has no babies, so Dart pops its printName from the call stack:

You’ve also finished iterating through Hoppy’s babies, so its printName function finishes normally. Dart pops it off the stack:

Mommy’s printName function was also in the middle of looping through its babies. Because the state is saved in the stack frame, Dart knows the next baby after Hoppy is Floppy.

The same process continues for Floppy’s babies and Moppy’s babies. Finally, when you’ve finished recursing through all Mommy’s babies, this printName function finishes, and Dart can pop it off the stack:

The main function also completes now, so Dart pops it off the stack. The call stack is empty, and your program is complete:

Replacing Recursion With a Loop and a Stack

As the chapter mentioned earlier, you can convert any recursive function to an iterative one. Sometimes, though, you need an extra data structure to do so. You learned how Dart implements recursion using an internal stack. You can do the same thing by hand with your stack.

You’ll find the stack.dart file you created in Chapter 4, “Stacks”, in the lib folder of your starter project. Open the file with your main function and import your stack:

import 'package:starter/stack.dart';

Then, write the following code:

void printNamesIteratively(Rabbit rabbit) {
  // 1
  final stack = Stack<Rabbit>();
  stack.push(rabbit);
  // 2
  while (stack.isNotEmpty) {
    // 3
    Rabbit current = stack.pop();
    print(current.name);
    // 4
    final babies = current.babies;
    if (babies == null) continue;
    // 5
    for (final baby in babies.reversed) {
      stack.push(baby);
    }
  }
}

Here’s what’s happening:

1. You initialize the stack by pushing the first rabbit. In this case, that will be Mommy.
2. As long as there’s a rabbit on the stack, you keep popping and pushing.
3. Rather than waiting to handle all the babies first, this algorithm pops a rabbit off the stack before moving on to its babies.
4. If no babies exist, you backtrack and pop the next rabbit off the stack.
5. If a rabbit does have babies, though, you queue them up for future handling by pushing them to the stack. There isn’t any special requirement to use babies.reversed rather than just babies. Either way, you visit each rabbit once. The only reason this function used reversed was to mimic the same order Dart gave in the recursive version.

Call your function at the bottom of main like so:

printNamesIteratively(family);

Run that, and it’ll print the rabbit names in the same order as before:

Mommy
Hoppy
Bunny
Honey
Sunny
Floppy
Doozy
Woozy
Moppy
Nosey
Mosey
Toesy
Rosey

The key takeaway is that you can use iteration and a stack to accomplish the same thing as recursion. There’s nothing magical about recursion.

Note: You can also use a queue rather than a stack when iterating over a tree-like data structure. The main difference is the order in which you visit the elements. You’ll learn more about this in a future chapter.

Now that you understand how recursion works, it’s time to come back to the question of the stack overflow error you saw at the beginning of the chapter.

What Is a Stack Overflow?

When a recursive function keeps calling itself, Dart keeps adding the function state to the call stack. Each stack frame on the stack takes a bit of the memory the system has allocated to your program. Eventually, that memory runs out, and you have a stack overflow.

When Not to Use Recursion

An oft-used example when teaching recursion is the Fibonacci sequence. For a refresher, the Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, … Besides the first two, every number in the sequence is the sum of the two before it.

Unoptimized Recursive Fibonacci Function

You can find the value of the nth number in the sequence using a recursive function like so:

int fibonacci(int n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

The base case is when n is less than or equal to one, which means you’ve reached the beginning of the sequence. The recursive case takes the two previous values before n and adds them to find n.

The code is very compact and looks quite elegant. The problem is it’s inefficient. To see why, add a print statement to the beginning of fibonacci:

print('fibonacci($n)');

Then, run the following from main:

final value = fibonacci(5);
print('value: $value');

Here is the printout:

fibonacci(5)
fibonacci(4)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(1)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(1)
value: 5

For every function call, you make two more recursive calls. Here’s the same information in visual form:

You’re repeating a lot of work. For example, look for f(3), and it’s there twice. Look for f(2), and you see it three times. You did the work to calculate fibonacci(3) and fibonacci(2) once. Repeating that work is a complete waste of time. Because the amount of work nearly doubles for every increase in n, the time complexity of this algorithm is O(2^n). This is known as exponential time complexity.

Note: O(2^n) is much worse than O(n^2), which is only quadratic complexity. Take n to be 30, for example. Thirty squared is merely 900. Two to the 30th power, though, is 1,073,741,824. Much worse!

Optimizing With Memoization

A major optimization technique in this sort of scenario is to store the computed values and just look them up when needed. This is known as memoization.

Note: You pronounce the -ization part of memoization the same as in memorization, but say “memo” first. That’s /ˌmɛmoʊaɪˈzeɪʃən/, if you’re familiar with the phonetic alphabet.

Replace your inefficient fibonacci function with the following optimized one:

int fibonacci(int n, [Map<int, int>? memo]) {
  print('fibonacci($n)');
  memo ??= {};
  if (n <= 1) return n;
  if (!memo.containsKey(n)) {
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  }
  return memo[n]!;
}

This time you used a map called memo to cache the Fibonacci values you’ve already calculated. Now, you only need to perform the recursive calls when memo doesn’t contain the value. This saves a lot of work.

Run the code again, and this time you see the shortened output:

fibonacci(5)
fibonacci(4)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(1)
fibonacci(2)
fibonacci(3)
value: 5

Graphically, that looks like so:

Your time complexity has turned into a much more acceptable O(n).

Preferring Iteration

Memoization is good, and it has its place, but this is a situation where there’s no need to use recursion at all. Why not use simple iteration?

Replace fibonacci with the following iterative version:

int fibonacci(int n) {
  if (n <= 1) return n;

  int first = 1;
  int second = 1;

  for (int i = 3; i <= n; i++) {
    int temp = first + second;
    first = second;
    second = temp;
  }

  return second;
}

This time, you used a simple for loop to calculate the successive Fibonacci values. The time complexity is still linear, like your memoized version, but this version is easier to reason about because you don’t have to worry about recursion or memoization.

Choosing Between Recursion and Iteration

So when do you need to use recursion, and when can you just use iteration?

Think back to the rabbit example earlier in the chapter. The branching nature of the problem made it difficult to use a simple loop. It was still possible but required the help of a stack.

When learning about recursion, I found Al Sweigart’s advice helpful in the talk Recursion for Beginners: A Beginner’s Guide to Recursion. The general rule of thumb is to use recursion whenever the following two conditions are true:

1. You have a tree-like data structure.
2. You need to backtrack to visit different branches of the tree.

The rest of the time, iteration with a simple loop is probably all you need.

The rabbit family had a tree-like data structure, and visiting each of the babies in different branches of the tree required backtracking. That made it a good candidate for recursion. Comparing the recursive and iterative approaches, it was easier to use recursion than to manage iteration with the help of a stack.

On the other hand, calculating the Fibonacci sequence, counting to 10 and finding the squared integers from 1 to 100 can all be accomplished with a simple loop. You don’t even need a helper stack. If you can solve a problem using simple iteration, go for it! Don’t use recursion just because you know how.

In the first edition of this book, I implemented the toString method of LinkedList recursively in Chapter 5, “Linked Lists.” But while writing this chapter for the book’s second edition, I realized a linked list is not very tree-like. Also, you don’t need to backtrack to visit every list member. Because of that, I rewrote toString using a loop. That also meant I could delay this new recursion chapter until the Trees section, where it belongs.

This chapter has given you an informal introduction to trees. In the following chapters, you’ll learn a lot more. Recursion will be an important tool to help you along the way.

Challenges

Here are a few challenges to test your understanding of what you learned in this chapter. You can find the answers in the Challenge Solutions section and in the supplementary materials that accompany the book.

Challenge 1: Would You Rather

Based on the advice at the end of the chapter, would it likely be easier to use iteration or recursion for the following problems:

1. Printing all the file names on your hard drive.
2. Calculating n factorial.
3. Tracking a person’s matrilineal line (mother’s mother’s mother) in a family tree.
4. Parsing JSON.

Challenge 2: How Many

Using the Rabbit class and family object you wrote earlier in the chapter, create a function that returns the total number of family members.

The function signature looks like so:

int countSize(Rabbit family)

Challenge 3: Even Faster

Use memoization to convert your iterative fibonacci function from O(n) to amortized O(1), assuming the function will be called many times.

Key Points

• A recursive function is a function that calls itself.
• The base case is the condition when recursion stops.
• Dart implements recursion with a call stack, which uses the stack data structure internally.
• Each function on the call stack is known as a stack frame.
• A stack overflow error occurs when recursion continues unchecked and fills the call stack beyond its memory limit.
• Memoization refers to caching the results of expensive function calls, which improves efficiency.
• Any recursive function can be converted to an iterative function, though potentially needing a helper data structure like a stack or queue.
• Recursion is useful if your problem has a tree-like data structure and requires backtracking. Otherwise, iteration is likely better.