Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

7. Chapter 7 Solutions
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

Solution to Exercise 1

One way to count by fives to 100 iteratively is like so:

for (int i = 5; i <= 100; i += 5) {
  print(i);
}

You can accomplish the same task recursively like this:

void countByFivesRecursively([int i = 5]) {
  if (i > 100) return;
  print(i);
  countByFivesRecursively(i + 5);
}

Solution to Exercise 2

You can print the square integers up to 100 iteratively using a while loop:

int i = 1;
int square = 1;
while (square <= 100) {
  print(square);
  i++;
  square = i * i;
}
void printSquaresRecursively([int i = 1]) {
  final square = i * i;
  if (square > 100) return;
  print(square);
  printSquaresRecursively(i + 1);
}

Solution to Challenge 1

  1. A computer’s file system uses a tree-like structure of folders and files. To print every file name, you would need to backtrack after completing the files in any particular folder. So recursion would be an appropriate solution.
  2. There is nothing especially tree-like about calculating a factorial, so using iteration would be just fine.
  3. While a family tree is indeed tree-like, no backtracking is needed to follow the matrilineal line, so iteration would be sufficient.
  4. JSON uses a tree-like structure with nested objects and arrays. To navigate in and out of them, backtracking would be required. So recursion would be an appropriate solution here.

Solution to Challenge 2

First, you count the current rabbit, and then you recursively add any babies it has. The base case is when a rabbit has no babies, or you’ve finished iterating through them.

int countSize(Rabbit family) {
  int count = 1;
  final babies = family.babies;
  if (babies != null) {
    for (final baby in babies) {
      count += countSize(baby);
    }
  }
  return count;
}

Solution to Challenge 3

Although you could use a map, an efficient solution would be to use a list to cache the numbers of the Fibonacci sequence that you’ve already calculated. The index is n, and the value is the number in the sequence.

// 1
final List<int> _memo = [0, 1, 1];

int fibonacci(int n) {
  // 2
  if (n < _memo.length) {
    return _memo[n];
  }
  // 3
  for (int i = _memo.length; i <= n; i++) {
    int temp = _memo[i - 1] + _memo[i - 2];
    _memo.add(temp);
  }

  return _memo[n];
}
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 reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now