Освоение динамической рекурсии в JavaScript: пошаговое руководство на примере Фибоначчи

Рекурсия

Рекурсия — это метод программирования, при котором функция вызывает сама себя для решения проблемы. Он часто используется, когда решение проблемы может быть выражено в виде уменьшенной версии той же самой проблемы. Рекурсия — мощный инструмент в программировании, но его использование может оказаться сложным. Одной из распространенных проблем с рекурсией является возможность бесконечных циклов, если базовый случай не определен правильно.

Динамическая рекурсия

Динамическая рекурсия — это тип рекурсии, при котором функция может изменять свои собственные параметры или состояние при вызове самой себя. Этот метод особенно полезен при работе с проблемами, которые включают в себя несколько подзадач, поскольку он позволяет функции отслеживать ее ход и избегать избыточных вычислений.

Давайте рассмотрим пример динамической рекурсии в JavaScript. Рассмотрим задачу вычисления n-го числа в последовательности Фибоначчи. Последовательность Фибоначчи определяется следующим образом:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) for n >= 2

Вот динамическая рекурсивная реализация функции fib в JavaScript:

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

В этой реализации мы используем объект с именем memo для хранения результатов предыдущих вычислений. Это позволяет нам избежать избыточных вычислений, проверяя, был ли результат для данного n уже рассчитан и сохранен в memo. Если это так, мы просто возвращаем это значение, а не пересчитываем его.

Функция принимает необязательный параметр memo, который изначально является пустым объектом. Поскольку функция вызывает себя рекурсивно, она передает один и тот же объект memo при каждом последующем вызове. Это позволяет каждому рекурсивному вызову обращаться к предыдущим результатам, хранящимся в memo.

В базовом случае, когда n меньше или равно 1, мы просто возвращаем n. В противном случае мы вычисляем n-е число Фибоначчи, рекурсивно вызывая функцию fib с n-1 и n-2, передавая также объект memo. Мы складываем результаты этих двух рекурсивных вызовов и сохраняем результат в memo. Наконец, мы возвращаем результат.

Вот пример использования функции fib:

console.log(fib(6)); // Output: 8

В этом примере мы вызываем функцию fib с n равным 6. Объект memo изначально пуст, поэтому функция начинает с рекурсивного вычисления fib(5) и fib(4). Эти рекурсивные вызовы, в свою очередь, вычисляют fib(4) и fib(3) и fib(3) и fib(2) соответственно. Вызов fib(3) является дубликатом, но поскольку его результат уже хранится в memo, он просто извлекается оттуда, а не пересчитывается. Затем функция вычисляет fib(2) и fib(1) и сохраняет их результаты в memo. Наконец, функция возвращает 8, что является 6-м числом Фибоначчи.

Заключение

В заключение, динамическая рекурсия — это мощный инструмент в программировании, который позволяет функциям изменять свои собственные параметры или состояния, когда они рекурсивно вызывают себя. Это может быть полезно при работе с проблемами, которые включают в себя несколько подзадач, поскольку позволяет функции отслеживать ее ход и избегать избыточных вычислений. Пример вычисления последовательности Фибоначчи демонстрирует эффективность динамической рекурсии при решении задач.