Понављање
Итерација је понављање процеса. Ученик који иде у школу понавља поступак одласка у школу сваки дан до матуре. Барем једном или два пута месечно идемо у продавницу да купимо производе. Овај поступак понављамо сваког месеца. У математици Фибоначијев низ прати својства понављања задатака. Размотримо Фибоначијеву секвенцу где су прва два броја 0 и 1, а сви остали бројеви су збир претходна два броја.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Кораци понављања
Фибоначијева формула се може записати као,
Ф (н) = Ф (н - 1) + Ф (н - 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
Алгоритам дат у наставку даје н-ти Фибонаццијев број.
Рекурзија
Сваки пут када добијемо нови Фибоначијев број (н-ти број) тај н-ти број је заправо (н - 1) -ти број када пронађемо (н + 1) -ти Фибонацци као следећи н-ти Фибонацци. Као што видимо горе поменуте кораке итерације: ако је н = 2 тада
Фибоначи (2) = Фибоначи (2 - 1) + Фибоначи (2 - 2) = Фибоначи (1) + Фибоначи (0) = 1 + 0 = 1
Сада желимо да генеришемо фибоначи (3), то је н = 3.
Фибоначи (3) = Фибоначи (3 - 1) + Фибоначи (3 - 2) = Фибоначи (2) + Фибоначи (1) = 1 + 1 = 2
То значи да се сваки пут када н повећава вредност струје (н - 1) тх и (н - 2) тх фибонаћи такође повећава. Али заморно је пратити (н - 1) -ти и (н - 2) -ти фибонаћи за сваки н. Шта кажете на то да напишете методу која себе позива да сама понови задатак итерације?
Метода која себе позива назива се рекурзивном методом. Рекурзивна метода мора имати основни случај када програм престаје да позива себе. Наш основни случај за Фибоначијеву серију је фибоначи (0) = 0 и фибоначи (1) = 1. Иначе, Фибоначијева метода себе назива два пута - фибоначи (н - 1) и фибоначи (н - 2). Затим их додаје да би добили фибоначи (н). Рекурзивна метода за проналажење н-тог Фибоначија може се записати као -
Ако пажљиво погледамо, рекурзија следи својство стека. Решава мање потпроблеме да би се добило решење проблема. За н> 1 извршава последњу линију. Дакле, ако је н = 6, функција позива и додаје фибоначијеве (6 - 1) и фибоначијеве (6 - 2). фибонацци (6 - 1) или фибонацци (5) позива и додаје фибонацци (5 - 1) и фибонацци (5 - 2). Ова рекурзија се наставља све док 6 не досегне своју основну вредност случаја која је фибонацци (0) = 0 или фибонацци (1) = 1. Једном када погоди основни случај додаје две основне вредности и иде горе док не добије вредност фибонацци ( 6). Испод је приказ дрвећа рекурзије.
Дрво рекурзије
Као што видимо, колико рекурзија може бити моћна. Само један ред кода прави дрво горе (последњи ред кода горе укључујући основне случајеве). Рекурзија одржава хрпу и иде дубље док не дође до основног кућишта. Динамичко програмирање (ДП): Рекурзија је једноставна за разумевање и кодирање, али може бити скупа у погледу времена и меморије. Погледајте доле дрво рекурзије. Лево подстабло које почиње са фиб (4) и десно подстабло које почиње са фиб (4) потпуно су исте. Они генеришу исти резултат који је 3, али два пута раде исти задатак. Ако је н велики број (пример: 500000), онда рекурзија може учинити програм веома спорим јер би исти подзадатак позивао више пута.
рекурзија Окружен дрветом
Да би се избегао овај проблем, може се користити динамичко програмирање. У динамичком програмирању можемо користити претходно решени подзадатак за решавање будућих задатака истог типа. Ово је начин да се смањи задатак за решавање изворног проблема. Имајмо низ фиб [] где чувамо претходно решена решења подзадатака. Већ знамо да је фиб [0] = 0 и фиб [1] = 1. Спремимо ове две вредности. Сад, колика је вредност фиб [2]? Како су фиб [0] = 0 и фиб [1] = 1 већ ускладиштени, само морамо рећи фиб [2] = фиб [1] + фиб [0] и то је све. На исти начин можемо генерисати фиб [3], фиб [4], фиб [5], ……, фиб [н]. Претходно решени подзадаци се позивају да би добили следећи подзадатак док оригинални задатак не буде решен, што смањује сувишни прорачун.
