generate the Fibonacci sequence.

// Challenge: generate the Fibonacci sequence.
// Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13...
// Input: n = 8 (how many numbers we want)
// Expected output: [0, 1, 1, 2, 3, 5, 8, 13]

// Solution 1: iterative (the preferred one in interviews because it's efficient).
List<int> fibonacci(int n) {
  if (n <= 0) return [];
  if (n == 1) return [0];

  final sequence = [0, 1];
  while (sequence.length < n) {
    final last = sequence[sequence.length - 1];
    final secondToLast = sequence[sequence.length - 2];
    sequence.add(last + secondToLast);
  }
  return sequence;
}

// Solution 2: recursive for the nth value.
// Elegant but inefficient (it recalculates the same thing many times).
// Good for explaining recursion, bad for large numbers.
int fibonacciRecursive(int n) {
  if (n <= 1) return n;
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

void main() {
  print(fibonacci(8)); // [0, 1, 1, 2, 3, 5, 8, 13]
  print(fibonacci(1)); // [0]
  print(fibonacci(0)); // [] (edge case)

  print(fibonacciRecursive(7)); // 13 (the value at position 7)

  // Explanation:
  // The iterative version starts with [0, 1] and keeps adding the last two
  // until it has n numbers. It's O(n). The recursive version is "prettier"
  // but O(2^n): for large n it becomes extremely slow because it recalculates
  // the same values over and over. In an interview, mention that it
  // can be optimized with memoization if they ask you to.
}