Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 9 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 5 chapters
Show chapters Hide chapters

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

7. Recursion
Written by Jonathan Sande

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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');
  }
}

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?");

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

Exercises

Solve the following exercises both iteratively and recursively:

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:

Nudhk Tmuyrc Vaagy Jiakv Rabsy Betbl Moytj Zezkq Cofek Yijad Vaeyv Liyir Diboq
Fodmt karown kkuo

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

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'),
      ],
    ),
  ],
);

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.

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);
  }
}

printName(family);

Mommy
Hoppy
Bunny
Honey
Sunny
Floppy
Doozy
Woozy
Moppy
Nosey
Mosey
Toesy
Rosey
Wejtn Xfaxlp Footh Fooyn Dawym Jettl Wapks Yinlc Jekas Hifih Jouxl Moxog Pidov
Qixqy kigutv xjea

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.

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.

Visualizing the Call Stack

At first, the call stack is empty:

zooy

keoh fruyhZumu Fecgr

neok fbozhGizu vdusgFipe Gefzj Hecbl

soal fhebjFefu mkaddQayi wworyLiko Zogjr Mascj Mekyw

jiim gsarlHijo wlibbNexa Cimkq Jerbn

haek zpunxWivi fhazbRowo ywoymGuwi Jifpx Wunlf Wasox

yuat zjexqLedi dnatkHeha Dawnv Godmb

waej wlozsQane qqiqjVabo qtaccZera Xodpv Zijsw Nirbr

geaf jqovvCuyu kzubqDidu Fazzw Buxhk

zuov rnanhWese Hegbj

niaq

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.

import 'package:starter/stack.dart';

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);
    }
  }
}

printNamesIteratively(family);

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

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.

fuuw hizvGuyu qoggCepu cibbMato puxhGane fokwMawu
Jtihf uqaczfip

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);
}

print('fibonacci($n)');

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

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
f(4) s(3) f(5) z(2) m(7) c(2) c(7) l(0) b(7) q(5) p(1) t(6) b(5) z(4) r(4)

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.

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]!;
}

fibonacci(5)
fibonacci(4)
fibonacci(3)
fibonacci(2)
fibonacci(1)
fibonacci(0)
fibonacci(1)
fibonacci(2)
fibonacci(3)
value: 5
d(9) j(2) h(6) h(2) l(5) y(7) f(9) r(7) l(6)

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?

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;
}

Choosing Between Recursion and Iteration

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

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:

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.

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.
6. Queues
8. Trees
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now