Повторение
Итерацията е повторение на процес. Ученик, който ходи на училище повтаря процеса на ходене на училище всеки ден до дипломирането си. Отиваме в хранителен магазин поне веднъж или два пъти месечно, за да купим продукти. Повтаряме този процес всеки месец. В математиката последователността на Фибоначи също следва свойствата на повторението на задачата. Нека разгледаме последователността на Фибоначи, където първите две числа са 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) th и (n - 2) th фибоначи също се увеличава. Но е уморително да следите (n - 1) -и и (n - 2) -ви фибоначи за всеки n. Какво ще кажете за писане на метод, който се призовава да повтаря задачата за итерация от себе си?
Метод, който се извиква, се нарича рекурсивен метод. Рекурсивният метод трябва да има основен случай, когато програмата спира да се самоизвиква. Нашият основен случай за сериите на Фибоначи е fibonacci (0) = 0 и fibonacci (1) = 1. В противен случай методът на Fibonacci се нарича два пъти - fibonacci (n - 1) и fibonacci (n - 2). След това ги добавя, за да получат fibonacci (n). Рекурсивен метод за намиране на n-ия Фибоначи може да се запише като -
Ако погледнем внимателно, рекурсията следва свойството на стека. Той решава по-малки подпроблеми, за да получи решението на проблема. При n> 1 изпълнява последния ред. Така че, ако n = 6, функцията извиква и добавя фибоначи (6 - 1) и фибоначи (6 - 2). fibonacci (6 - 1) или fibonacci (5) извиква и добавя fibonacci (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] по същия начин. По-рано решените подзадачи се извикват, за да получат следващата подзадача, докато оригиналната задача не бъде решена, като по този начин намалява излишното изчисление.
