Write a function to generate the first N Fibonacci numbers. Implement both iterative and recursive solutions and explain the time complexity of each.

Overview

The Fibonacci sequence is a series where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

Formula:

F(n) = F(n-1) + F(n-2)

F(0) = 0

F(1) = 1

This classic problem demonstrates recursion, dynamic programming, and algorithm optimization techniques essential for technical interviews.

Approach 1: Iterative Solution (Optimal)

Most efficient approach using a simple loop.

dartCopy
List<int> fibonacciIterative(int n) {
  if (n <= 0) return [];
  if (n == 1) return [0];

  List<int> result = [0, 1];

  for (int i = 2; i < n; i++) {
    result.add(result[i - 1] + result[i - 2]);
  }

  return result;
}

void main() {
  print(fibonacciIterative(10));
  // Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
}

Time Complexity: O(n) - single loop iteration Space Complexity: O(n) - stores all n numbers

Approach 2: Recursive (Naive)

Direct implementation of mathematical definition. Warning: Extremely slow for large n!

dartCopy
int fibonacciRecursive(int n) {
  if (n <= 1) return n;
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

List<int> getFibSequence(int n) {
  return List.generate(n, (i) => fibonacciRecursive(i));
}

void main() {
  print(getFibSequence(10));
  // Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

  // DON'T try large values - exponential time!
  // fibonacciRecursive(40) takes many seconds!
}

Time Complexity: O(2^n) - exponential, very slow! Space Complexity: O(n) - recursion call stack

Why so slow? Massive redundant calculations.

Approach 3: Memoized Recursive (Dynamic Programming)

Cache computed values to avoid redundancy.

dartCopy
class FibonacciMemo {
  final Map<int, int> _cache = {0: 0, 1: 1};

  int fib(int n) {
    if (_cache.containsKey(n)) {
      return _cache[n]!;
    }

    _cache[n] = fib(n - 1) + fib(n - 2);
    return _cache[n]!;
  }

  List<int> getSequence(int n) {
    return List.generate(n, (i) => fib(i));
  }
}

void main() {
  final fibonacci = FibonacciMemo();
  print(fibonacci.getSequence(10));

  // Now fast even for large values!
  print(fibonacci.fib(50));  // Instant!
}

Time Complexity: O(n) - each value computed once Space Complexity: O(n) - cache + recursion stack

Approach 4: Space-Optimized

Generate sequence without storing all values.

dartCopy
int nthFibonacci(int n) {
  if (n <= 1) return n;

  int prev = 0, curr = 1;

  for (int i = 2; i <= n; i++) {
    int next = prev + curr;
    prev = curr;
    curr = next;
  }

  return curr;
}

void main() {
  print(nthFibonacci(10));  // 55
  print(nthFibonacci(20));  // 6765
}

Time Complexity: O(n) Space Complexity: O(1) - only 2 variables!

Approach 5: Generator Function (Dart-Specific)

Lazy evaluation using Dart generators.

dartCopy
Iterable<int> fibonacciGenerator(int n) sync* {
  if (n <= 0) return;

  int prev = 0, curr = 1;
  yield prev;
  if (n == 1) return;
  yield curr;

  for (int i = 2; i < n; i++) {
    int next = prev + curr;
    yield next;
    prev = curr;
    curr = next;
  }
}

void main() {
  // Lazy - values generated on demand
  for (var num in fibonacciGenerator(10)) {
    print(num);
  }

  // Or convert to list
  print(fibonacciGenerator(10).toList());
}

Comparison of Approaches

Complete Working Example

dartCopy
class Fibonacci {
  // Iterative (recommended)
  static List<int> iterative(int n) {
    if (n <= 0) return [];
    if (n == 1) return [0];

    List<int> result = [0, 1];
    for (int i = 2; i < n; i++) {
      result.add(result[i - 1] + result[i - 2]);
    }
    return result;
  }

  // Nth number only
  static int nth(int n) {
    if (n <= 1) return n;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
      int next = prev + curr;
      prev = curr;
      curr = next;
    }
    return curr;
  }

  // Generator
  static Iterable<int> generate(int n) sync* {
    if (n <= 0) return;
    int prev = 0, curr = 1;
    yield prev;
    if (n == 1) return;
    yield curr;

    for (int i = 2; i < n; i++) {
      int next = prev + curr;
      yield next;
      prev = curr;
      curr = next;
    }
  }
}

void main() {
  print(Fibonacci.iterative(10));
  print(Fibonacci.nth(10));
  print(Fibonacci.generate(10).toList());
}

Edge Cases

dartCopy
void testEdgeCases() {
  assert(fibonacciIterative(0).isEmpty);
  assert(fibonacciIterative(1) == [0]);
  assert(fibonacciIterative(2) == [0, 1]);
  assert(nthFibonacci(0) == 0);
  assert(nthFibonacci(1) == 1);
}

Best Practices

1. Use Iterative for General Cases

dartCopy
// ✅ Optimal
List<int> fibonacci(int n) => Fibonacci.iterative(n);

2. Never Use Naive Recursion

dartCopy
// ❌ O(2^n) - extremely slow
int fib(int n) => n <= 1 ? n : fib(n-1) + fib(n-2);

3. Handle Edge Cases

dartCopy
List<int> fibonacci(int n) {
  if (n <= 0) return [];
  if (n == 1) return [0];
  // ... logic
}

Interview Tips

When asked about Fibonacci:

1. Start with iterative - shows you know optimal approach
2. Mention naive recursive but explain O(2^n) problem
3. Discuss memoization for DP knowledge
4. Consider space optimization

Follow-ups:

• "Find nth without storing all?" → Space-optimized approach
• "Can we do better than O(n)?" → Matrix exponentiation O(log n)
• "What if n is huge?" → Use BigInt

Resources

• Fibonacci Number - Wikipedia
• Dynamic Programming
• Dart Generators