7. Chapter 7 Solutions

Written by Jonathan Sande

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

Here is how you would accomplish the same task recursively:

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

Here are a few notes:

1. Initialize the list with the first three Fibonacci values.
2. If your cached value is already in the list, you can return it immediately with an O(1) time complexity.
3. For new Fibonacci numbers that are not yet in the list, you must calculate the values. This has an O(n) time complexity, but since you cache every value leading up to it, you’ll only need to do this once.

If you only ever call fibonacci once, it’ll still have a linear time complexity, but since future calls for values of n less than or equal to previous ones have a constant time, the overall efficiency will average out to constant time. This is also known as amortized constant time.

One more thing to be aware of is that for any value of n higher than 92, a signed 64-bit integer will overflow.