Optional positional parameter in Dart

Question

I'm studying recursion and I wrote this method to calculate the N° number of the Fibonacci series:

fibonacci(int n, Map memo) {

  if (memo.containsKey(n)) return memo[n];  // Memo check
  if (n <= 2) return 1;  // base case
  // calculation
  memo[n] = fibonacci(n - 1, memo) + fibonacci((n - 2), memo);
  return memo[n];
}

I think it doesn't need to be explained, my problem is just how to call this function from the main, avoiding providing an empty Map.

this is how I call the function now:

fibonacci(n, {});

But I would rather prefer to call it just like this:

fibonacci(n);

Answer 1

The canonical approach is to make memo optional, and use a fresh map if the memo argument is omitted. Because you want to change and update the map, you can't use a default value for the parameter, because default values must be constant, and constant maps are not mutable.

So, written very concisely:

int fibonacci(int n, [Map<int, int>? memo]) {
  if (n <= 2) return 1;
  return (memo ??= {})[n] ??= fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
}

The ??= operator assigns to the right-hand side if the value is null. It's used both to initialize memo to a new map if the argument was omitted, and to update the map if a cached value wasn't present.

I'd actually reconsider using a map. We know that the Fibonacci computation will compute a value for every prior number down to 1, so I'd just use a list instead:

int fibonacci(int n, [List<int?>? memo]) {
  if (n <= 2) return 1;
  return (memo ??= List<int?>.filled(n - 2))[n - 3] ??= 
     fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
}

That should work just like the map. (I subtract 3 from n when doing the lookup because no value below 3 needs the list - it's handled by the prior if).