Итерация
Итерация - это повторение процесса. Ученик, который ходит в школу, повторяет процесс посещения школы каждый день до окончания учебы. Мы ходим в продуктовый магазин хотя бы один или два раза в месяц, чтобы купить продукты. Мы повторяем этот процесс каждый месяц. В математике последовательность Фибоначчи также следует свойствам повторения задачи. Давайте рассмотрим последовательность Фибоначчи, где первые два числа равны 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). Затем он складывает их, чтобы получить fibonacci (n). Рекурсивный метод поиска n-го числа Фибоначчи может быть записан как -
Если мы внимательно посмотрим, рекурсия следует свойству стека. Он решает более мелкие подзадачи, чтобы получить решение проблемы. При n> 1 выполняется последняя строка. Итак, если n = 6, функция вызывает и добавляет фибоначчи (6-1) и фибоначчи (6-2). fibonacci (6-1) или fibonacci (5) вызывает и добавляет фибоначчи (5-1) и fibonacci (5-2). Эта рекурсия продолжается до тех пор, пока 6 не достигнет своего значения базового случая, которое является fibonacci (0) = 0 или fibonacci (1) = 1. Как только он достигает базового случая, он добавляет два базовых значения и поднимается до значения fibonacci ( 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]. Ранее решенные подзадачи вызываются для получения следующей подзадачи до тех пор, пока исходная задача не будет решена, что сокращает избыточные вычисления.
