Из за чего ломается рекурсия при работе с большими числами

Из-за чего ломается рекурсия при работе с большими числами

Рекурсия — мощный инструмент программирования, но она имеет серьёзные ограничения при работе с большими числами и глубокой вложенностью. Основная проблема — переполнение стека вызовов (Stack Overflow).

Call Stack и его лимиты

В JavaScript каждый вызов функции добавляется в call stack (стек вызовов). Размер этого стека ограничен и зависит от браузера и среды выполнения:

• Chrome: ~10,000-15,000 вложенных вызовов
• Firefox: ~30,000+ вложенных вызовов
• Safari: ~15,000+ вложенных вызовов
• Node.js: ~10,000-15,000 вложенных вызовов

Когда глубина рекурсии превышает этот лимит, возникает RangeError: Maximum call stack size exceeded.

Пример проблемы

// Простая рекурсивная функция — подсчёт
function countdown(n) {
  if (n === 0) {
    console.log('Done!');
    return;
  }
  console.log(n);
  countdown(n - 1); // рекурсивный вызов
}

// Работает нормально
countdown(100); // OK

// Ломается при больших числах
countdown(50000); // RangeError: Maximum call stack size exceeded

Визуализация стека:

// При вызове countdown(5):
// Call Stack:
// ├─ countdown(5)
// │ ├─ countdown(4)
// │ │ ├─ countdown(3)
// │ │ │ ├─ countdown(2)
// │ │ │ │ ├─ countdown(1)
// │ │ │ │ │ ├─ countdown(0) <- base case

Почему это происходит?

1. Каждый вызов занимает память в стеке

Каждый рекурсивный вызов создаёт новый frame в call stack, который содержит:

• Локальные переменные
• Параметры функции
• Адрес для возврата
• Контекст выполнения (this)

function fibonacci(n) {
  // Каждый вызов требует памяти:
  // - переменная n
  // - адрес возврата
  // - контекст функции
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

fibonacci(50); // Очень медленно и может привести к переполнению

2. Множественные рекурсивные вызовы усугубляют проблему

Вот наглядный пример с Fibonacci:

// Дерево вызовов для fibonacci(5):
//                  fib(5)
//              /            \
//          fib(4)            fib(3)
//         /      \          /      \
//     fib(3)   fib(2)   fib(2)   fib(1)
//     /   \    /   \    /   \
//  fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
//  /  \
// fib(1) fib(0)

// Количество вызовов растёт экспоненциально!
// fib(10) = 177 вызовов
// fib(20) = 21,891 вызовов
// fib(50) = 40 миллиардов вызовов

Решения

1. Хвостовая рекурсия (Tail Call Optimization)

Если рекурсивный вызов — последний оператор в функции, некоторые движки оптимизируют код и переиспользуют frame стека. К сожалению, JavaScript не гарантирует TCO.

// Хвостовая рекурсия
function countdownTail(n, accumulator = 0) {
  if (n === 0) {
    return accumulator;
  }
  return countdownTail(n - 1, accumulator + n); // last call
}

countdownTail(50000); // Может работать в некоторых браузерах

**2. Мемоизация (Caching)

Для функций, которые вызываются многократно с одинаковыми аргументами, используй кеширование:

function fibonacci(n, cache = {}) {
  if (n in cache) return cache[n];
  if (n <= 1) return n;
  
  cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
  return cache[n];
}

fibonacci(50); // Очень быстро! O(n) вместо O(2^n)

3. Итеративный подход (циклы вместо рекурсии)

Это самое надёжное решение — замени рекурсию циклом:

// Вместо рекурсии
function sumRecursive(arr, index = 0) {
  if (index === arr.length) return 0;
  return arr[index] + sumRecursive(arr, index + 1);
}

// Используй цикл
function sumIterative(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

const bigArray = new Array(100000).fill(1);
sumIterative(bigArray); // Быстро и безопасно

4. Разделение работы (batching)

Делай работу небольшими порциями с использованием setTimeout или requestAnimationFrame:

async function processLargeDataset(data, batchSize = 100) {
  for (let i = 0; i < data.length; i += batchSize) {
    const batch = data.slice(i, i + batchSize);
    processBatch(batch);
    await new Promise(resolve => setTimeout(resolve, 0)); // yield
  }
}

Выводы

Рекурсия ломается при больших числах из-за:

• Ограничения Call Stack — каждый вызов требует памяти
• Экспоненциального роста вызовов — особенно в функциях типа Fibonacci
• Отсутствия TCO гарантий — JavaScript не оптимизирует хвостовую рекурсию

Практические рекомендации:

1. Избегай рекурсии для больших наборов данных
2. Если нужна рекурсия, используй мемоизацию
3. Переводи на итеративный подход (циклы)
4. Для очень больших операций используй батчинг с yield

Помни: рекурсия красива, но циклы быстрее и безопаснее!