CODEWITHSUNDEEP
dartrecursionparameter-passingoption-typeoptional-parameters
Peppinhood
Peppinhood

Reputation: 39

Optional positional parameter in Dart

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

Upvotes: 0

Views: 978

Answers (3)

lrn
lrn

Reputation: 71693

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).

Upvotes: 2

nvoigt
nvoigt

Reputation: 77304

There are multiple ways to do it. This is my personal favorite, because it also limits the function that is only used for internal means and it doesn't have the need to check every recursion, as you already know there is a map provided:

int fibonacci(int n) {
  return _fibonacci(n, {});
}

int _fibonacci(int n, Map<int, int> memo) {
  if (n <= 2) return 1;  // base case
  
  final previouslyCalculated = memo[n];  // Memo check
  
  if(previouslyCalculated != null) {
    return previouslyCalculated;
  }
  
  // calculation
  final next = _fibonacci(n - 1, memo) + _fibonacci((n - 2), memo);
  
  memo[n] = next;
  
  return next;
}

void main() {
  print(fibonacci(4));
}

As Dart does not support overloading, if you actually need both versions to be publicly available (or want both private) you would have to pick different names.

Please note that I added proper types to your methods and cleaned them up a bit for everything that would not compile once proper types are used. Make sure you always use proper types and don't rely on dynamic to somehow works it's magic. The compiler can only help you, if you are explicit about what you want to do. Otherwise they can only nod and let you run into any mistake you may have made. Be smart, let your compiler help, it will catch a lot of errors for you at compile time that you would otherwise have to spent countless hours on debugging.

Upvotes: 1

Peppinhood
Peppinhood

Reputation: 39

This is the solution I've found so far but looks very verbose and inelegant:

fibonacci(int n, [Map<int, int>? memo]) { 
memo == null ? memo = {} : null; // null check 
if (memo.containsKey(n)) return memo[n]; 
if (n <= 2) return 1; 
memo[n] = fibonacci(n - 1, memo) + fibonacci((n - 2), memo); 
return memo[n]; 
}

In this way I can call just:

fibonacci(n);

Upvotes: 0

Related Questions