Числа Фибоначчи с мемоизацией

Решение

Задача на числа Фибоначчи с мемоизацией — классическая для демонстрации понимания рекурсии, оптимизации и сложности алгоритмов. Это часто спрашивают на собеседованиях.

Проблема: Наивная рекурсия

Без оптимизации это работает очень медленно:

// ❌ НЕЭФФЕКТИВНО: O(2^n)
function fibonacciNaive(n: number): number {
  if (n <= 1) return n;
  return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);
}

// fibonacci(50) займет вечность! Будет 2^50 вызовов
// fibonacci(20) уже ~ 1 миллион вызовов

Почему медленно: Одно и то же значение вычисляется много раз. Например, fibonacci(5) вычисляет fibonacci(3) дважды, fibonacci(2) трижды и т.д.

Решение 1: Мемоизация (Caching)

Запоминаем результаты вычислений:

// ✅ ХОРОШО: O(n) с кешем
function fibonacci(n: number): number {
  const cache: Record<number, number> = {};
  
  function fib(num: number): number {
    // Проверяем, есть ли в кеше
    if (num in cache) {
      return cache[num];
    }
    
    // Базовый случай
    if (num <= 1) {
      return num;
    }
    
    // Вычисляем и сохраняем в кеш
    cache[num] = fib(num - 1) + fib(num - 2);
    return cache[num];
  }
  
  return fib(n);
}

console.log(fibonacci(0));  // 0
console.log(fibonacci(1));  // 1
console.log(fibonacci(10)); // 55
console.log(fibonacci(20)); // 6765
console.log(fibonacci(50)); // 12586269025

Анализ:

• Временная сложность: O(n) — каждое число вычисляется один раз
• Пространственная сложность: O(n) — кеш + стек вызовов
• Рекурсия по-прежнему используется, но очень эффективна

Решение 2: Мемоизация с замыканием

Более элегантный вариант:

function createFibonacci() {
  const cache: Record<number, number> = {};
  
  function fib(n: number): number {
    if (n in cache) return cache[n];
    if (n <= 1) return n;
    
    cache[n] = fib(n - 1) + fib(n - 2);
    return cache[n];
  }
  
  return fib;
}

const fibonacci = createFibonacci();

console.log(fibonacci(50)); // 12586269025

Преимущества:

• Кеш сохраняется между вызовами
• Защита от переполнения стека при малых n
• Кеш изолирован в замыкании

Решение 3: Декоратор мемоизации (HOF)

Универсальный способ кеширования:

function memoize<T extends (...args: any[]) => any>(
  fn: T
): T {
  const cache = new Map();
  
  return ((...args) => {
    const key = JSON.stringify(args);
    
    if (cache.has(key)) {
      return cache.get(key);
    }
    
    const result = fn(...args);
    cache.set(key, result);
    return result;
  }) as T;
}

const fibonacci = memoize((n: number): number => {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
});

console.log(fibonacci(50)); // 12586269025

Преимущества:

• Можно применить к любой функции
• Переиспользуемый код
• SOLID принцип (Single Responsibility)

Бонус: Итеративное решение O(n) время, O(1) память

Без рекурсии и кеша:

// ✅ ОПТИМАЛЬНО: O(n) время, O(1) память
function fibonacciIterative(n: number): number {
  if (n <= 1) return n;
  
  let prev = 0;  // fibonacci(0)
  let curr = 1;  // fibonacci(1)
  
  // Проходим от 2 до n
  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  
  return curr;
}

console.log(fibonacciIterative(0));  // 0
console.log(fibonacciIterative(1));  // 1
console.log(fibonacciIterative(10)); // 55
console.log(fibonacciIterative(50)); // 12586269025

Анализ:

• Временная сложность: O(n) — один цикл
• Пространственная сложность: O(1) — только две переменные
• Нет рекурсии, нет стека вызовов
• Самый эффективный способ!

Расширенное решение: Обработка больших чисел

Для очень больших n используем BigInt:

function fibonacciBigInt(n: number): bigint {
  if (n <= 1) return BigInt(n);
  
  let prev = 0n;
  let curr = 1n;
  
  for (let i = 2; i <= n; i++) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  
  return curr;
}

console.log(fibonacciBigInt(100)); // Работает без потери точности
console.log(fibonacciBigInt(1000)); // Тоже работает!

Сравнение всех подходов

Бенчмарк

// Наивная: fibonacci(40) ~ 5 секунд
// Мемоизация: fibonacci(1000) < 1мс
// Итеративная: fibonacci(10000) < 1мс

Рекомендации для собеседования

1. Начните с проблемы — объясните, почему наивная рекурсия медленна
2. Покажите мемоизацию — простое и элегантное решение
3. Предложите итеративный вариант — демонстрирует глубокое понимание
4. Обсудите памяти — рекурсия vs итерация
5. Упомяните BigInt — для реальных применений

Мой выбор для production: Итеративное решение — простое, быстрое, не требует доп. памяти. Для собеседования сначала мемоизация, потом итеративное.