Содержание
итерация
Итерация — это повторение процесса. Учащийся, который идет в школу, повторяет процесс посещения школы каждый день до окончания школы. Мы идем в продуктовый магазин по крайней мере один или два раза в месяц, чтобы купить продукты. Мы повторяем этот процесс каждый месяц. В математике последовательность Фибоначчи следует свойствам повторения задачи. Давайте рассмотрим последовательность Фибоначчи, где первые два числа равны 0 и 1, все остальные числа являются суммой двух предыдущих чисел.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Шаги итерации
Формула Фибоначчи может быть записана как,
F (n) = F (n — 1) + F (n — 2)
Фибоначчи (0) = 0
Фибоначчи (1) = 1
Фибоначчи (2) = Фибоначчи (1) + Фибоначчи (0) = 1 + 0 = 1
Фибоначчи (3) = Фибоначчи (2) + Фибоначчи (1) = 1 + 1 = 2
Фибоначчи (4) = Фибоначчи (3) + Фибоначчи (2) = 2 + 1 = 3
Фибоначчи (5) = Фибоначчи (4) + Фибоначчи (3) = 3 + 2 = 5
Фибоначчи (6) = Фибоначчи (5) + Фибоначчи (4) = 5 + 3 = 8
Приведенный ниже алгоритм возвращает n-е число Фибоначчи.
Рекурсия
Каждый раз, когда мы получаем новое число Фибоначчи (n-е число), n-е число фактически является (n — 1) -ым числом, когда мы находим (n + 1) -ое число Фибоначчи в качестве нашего следующего n-го числа Фибоначчи. Как мы видим вышеупомянутые шаги итерации: если n = 2, то
Фибоначчи (2) = Фибоначчи (2 — 1) + Фибоначчи (2 — 2) = Фибоначчи (1) + Фибоначчи (0) = 1 + 0 = 1
Теперь мы хотим сгенерировать фибоначчи (3), то есть n = 3.
Фибоначчи (3) = Фибоначчи (3 — 1) + Фибоначчи (3 — 2) = Фибоначчи (2) + Фибоначчи (1) = 1 + 1 = 2
Это означает, что каждый раз, когда n увеличивает значение текущего (n — 1) -го и (n — 2) -го Фибоначчи также увеличивается. Но утомительно отслеживать (n — 1) -й и (n — 2) -й фибоначчи для каждого n. Как насчет написания метода, который вызывает себя, чтобы повторить задачу итерации самостоятельно?
Метод, который вызывает себя, называется рекурсивным методом. У рекурсивного метода должен быть базовый случай, когда программа перестает вызывать себя. Наш базовый случай для рядов Фибоначчи: Фибоначчи (0) = 0 и Фибоначчи (1) = 1. В противном случае метод Фибоначчи вызывает себя дважды — Фибоначчи (n — 1) и Фибоначчи (n — 2). Затем он добавляет их, чтобы получить Фибоначчи (n). Рекурсивный метод для поиска n-го Фибоначчи может быть записан как —
Если мы посмотрим внимательно, рекурсия следует за свойством стека. Это решает меньшие подзадачи, чтобы получить решение проблемы. При n> 1 выполняется последняя строка. Таким образом, если n = 6, функция вызывает и добавляет Фибоначчи (6 — 1) и Фибоначчи (6 — 2). Фибоначчи (6-1) или Фибоначчи (5) вызывают и добавляют Фибоначчи (5-1) и Фибоначчи (5-2). Эта рекурсия продолжается до тех пор, пока 6 не достигнет своего базового значения, которое равно fibonacci (0) = 0 или fibonacci (1) = 1. Как только оно достигает базового случая, оно добавляет два базовых значения и идет вверх, пока не получит значение 6). Ниже приведено древовидное представление рекурсии.
Дерево рекурсии
Как мы видим, насколько мощной может быть рекурсия. Только одна строка кода составляет дерево выше (последняя строка кода выше, включая базовые случаи). Рекурсия поддерживает стек и идет дальше, пока не достигнет базового варианта. Динамическое программирование (DP): рекурсия проста для понимания и написания кода, но может быть дорогой с точки зрения времени и памяти. Посмотрите на дерево рекурсии ниже. Левое поддерево, начинающееся с fib (4), и правое поддерево, начинающееся с fib (4), точно такие же. Они генерируют один и тот же результат, который равен 3, но выполняют одну и ту же задачу дважды. Если n — большое число (пример: 500000), то рекурсия может сделать программу очень медленной, так как она будет вызывать одну и ту же подзадачу несколько раз.
рекурсия обведена
Чтобы избежать этой проблемы, можно использовать динамическое программирование. В динамическом программировании мы можем использовать ранее решенную подзадачу для решения будущей задачи того же типа. Это способ уменьшить задачу для решения исходной задачи. Давайте иметь массив fib [], в котором мы храним ранее решенные подзадачи. Мы уже знаем, что fib [0] = 0 и fib [1] = 1. Давайте сохраним эти два значения. Теперь, каково значение fib [2]? Поскольку fib [0] = 0 и fib [1] = 1 уже сохранены, мы просто должны сказать, что fib [2] = fib [1] + fib [0], и это все. Мы можем генерировать fib [3], fib [4], fib [5], ……, fib [n] таким же образом. Ранее решенные подзадачи вызываются для получения следующей подзадачи, пока исходная задача не будет решена, что сокращает избыточные вычисления.
