Освоение динамической рекурсии в 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-м числом Фибоначчи.
Заключение
В заключение, динамическая рекурсия — это мощный инструмент в программировании, который позволяет функциям изменять свои собственные параметры или состояния, когда они рекурсивно вызывают себя. Это может быть полезно при работе с проблемами, которые включают в себя несколько подзадач, поскольку позволяет функции отслеживать ее ход и избегать избыточных вычислений. Пример вычисления последовательности Фибоначчи демонстрирует эффективность динамической рекурсии при решении задач.