Zrozumienie rekurencji i formuły rekurencyjnej

Iteracja

Iteracja to powtarzanie procesu. Uczeń idący do szkoły powtarza proces chodzenia do szkoły codziennie aż do matury. Co najmniej raz lub dwa razy w miesiącu chodzimy do sklepu spożywczego, aby kupić produkty. Powtarzamy ten proces co miesiąc. W matematyce ciąg Fibonacciego jest również zgodny z właściwościami powtarzania zadań. Rozważmy ciąg Fibonacciego, w którym pierwsze dwie liczby to 0 i 1, wszystkie inne liczby są sumą dwóch poprzednich liczb.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

Kroki iteracji

Wzór Fibonacciego można zapisać jako:

F (n) = F (n - 1) + F (n - 2)
Fibonacci (0) = 0
Fibonacci (1) = 1
Fibonacci (2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
Fibonacci (3) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Fibonacci (4) = Fibonacci (3) + Fibonacci (2) = 2 + 1 = 3
Fibonacci (5) = Fibonacci (4) + Fibonacci (3) = 3 + 2 = 5
Fibonacci (6) = Fibonacci (5) + Fibonacci (4) = 5 + 3 = 8

Algorytm podany poniżej zwraca n-tą liczbę Fibonacciego.

Rekursja

Za każdym razem, gdy otrzymujemy nową liczbę Fibonacciego (n-tą liczbę), ta n-ta liczba jest w rzeczywistości (n - 1)-tą liczbą, gdy znajdziemy (n + 1) -ty Fibonacciego jako naszą następną n-tą liczbę Fibonacciego. Jak widzimy powyższe kroki iteracji: jeśli n = 2 to
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Teraz chcemy wygenerować fibonacciego (3), czyli n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Oznacza to, że za każdym razem, gdy n wzrasta, wartość prądu (n - 1) th i (n - 2) th fibonacci również wzrasta. Ale męczące jest śledzenie (n - 1) th i (n - 2) th fibonacci dla każdego n. A co powiesz na napisanie metody, która woła sama do powtórzenia zadania iteracji?

Metoda, która sama się wywołuje, jest nazywana metodą rekurencyjną. Metoda rekurencyjna musi mieć przypadek podstawowy, w którym program przestaje wywoływać siebie. Nasz podstawowy przypadek dla szeregu Fibonacciego to fibonacci (0) = 0 i fibonacci (1) = 1. W przeciwnym razie metoda Fibonacciego nazywa się dwukrotnie - fibonacci (n - 1) i fibonacci (n - 2). Następnie dodaje je, aby uzyskać fibonacci (n). Rekurencyjną metodę znajdowania n-tego Fibonacciego można zapisać jako -

Jeśli przyjrzymy się uważnie, rekurencja jest zgodna z właściwością stosu. Rozwiązuje mniejsze podproblemy, aby uzyskać rozwiązanie problemu. Dla n> 1 wykonuje ostatnią linię. Tak więc, jeśli n = 6, funkcja wywołuje i dodaje fibonacciego (6 - 1) i fibonacciego (6 - 2). fibonacci (6 - 1) lub fibonacci (5) wywołuje i dodaje fibonacci (5 - 1) i fibonacci (5 - 2). Ta rekursja trwa do momentu, gdy 6 osiągnie wartość swojego przypadku bazowego, czyli fibonacci (0) = 0 lub fibonacci (1) = 1. Gdy trafi w przypadek podstawowy, dodaje dwie wartości podstawowe i rośnie, aż uzyska wartość fibonacciego ( 6). Poniżej znajduje się drzewo reprezentujące rekursję.

Drzewo rekurencji

Jak widać, jak potężna może być rekurencja. Drzewo powyżej tworzy tylko jeden wiersz kodu (ostatni wiersz powyższego kodu, w tym przypadki bazowe). Rekursja zachowuje stos i idzie głębiej, aż osiągnie przypadek podstawowy. Programowanie dynamiczne (DP): Rekursja jest łatwa do zrozumienia i kodowania, ale może być kosztowna pod względem czasu i pamięci. Spójrz na drzewo rekurencji poniżej. Lewe poddrzewo zaczynające się od fib (4) i prawe poddrzewo zaczynające się od fib (4) są dokładnie takie same. Generują ten sam wynik, czyli 3, ale wykonują to samo zadanie dwukrotnie. Jeśli n jest dużą liczbą (na przykład: 500000), rekurencja może bardzo spowolnić program, ponieważ wielokrotnie wywoływałaby to samo zadanie podrzędne.

rekurencja - w kółku

Aby uniknąć tego problemu, można zastosować programowanie dynamiczne. W programowaniu dynamicznym możemy wykorzystać wcześniej rozwiązane podzadanie do rozwiązania przyszłych zadań tego samego typu. Jest to sposób na ograniczenie zadań związanych z rozwiązaniem pierwotnego problemu. Przygotujmy tablicę fib [], w której przechowujemy rozwiązane wcześniej podzadania. Wiemy już, że fib [0] = 0 i fib [1] = 1. Zapiszmy te dwie wartości. Jaka jest wartość fib [2]? Ponieważ fib [0] = 0 i fib [1] = 1 zostały już zapisane, wystarczy powiedzieć, że fib [2] = fib [1] + fib [0] i to wszystko. W ten sam sposób możemy wygenerować fib [3], fib [4], fib [5], ……, fib [n]. Wcześniej rozwiązane podzadania są wywoływane w celu uzyskania następnego podzadania, dopóki pierwotne zadanie nie zostanie rozwiązane, co zmniejsza zbędne obliczenia.