Rekurencja to podstawowe pojęcie w informatyce i matematyce, które pozwala funkcjom wywoływać się same, umożliwiając rozwiązywanie złożonych problemów poprzez etapy iteracyjne. Jedną z reprezentacji wizualnych powszechnie używaną do zrozumienia i analizowania wykonywania funkcji rekurencyjnych jest drzewo rekurencji. W tym artykule zbadamy teorię drzew rekurencyjnych, ich strukturę i znaczenie w zrozumieniu algorytmów rekurencyjnych.

Co to jest drzewo rekurencji?

Drzewo rekurencji to graficzna reprezentacja ilustrująca przebieg wykonywania funkcji rekurencyjnej. Zapewnia wizualny podział wywołań rekurencyjnych, pokazując postęp algorytmu w miarę jego rozgałęziania i ostatecznie osiągania przypadku podstawowego. Struktura drzewa pomaga w analizie złożoności czasowej i zrozumieniu procesu rekurencyjnego.

Struktura drzewa

Każdy węzeł w drzewie rekurencji reprezentuje określone wywołanie rekurencyjne. Początkowe wywołanie jest przedstawione na górze, a kolejne wywołania rozgałęziają się pod nim. Drzewo rośnie w dół, tworząc strukturę hierarchiczną. Współczynnik rozgałęzienia każdego węzła zależy od liczby wywołań rekurencyjnych wykonanych w ramach funkcji. Dodatkowo głębokość drzewa odpowiada liczbie wywołań rekurencyjnych przed osiągnięciem przypadku bazowego.

Obudowa podstawowa

Przypadek podstawowy służy jako warunek zakończenia funkcji rekurencyjnej. Określa moment, w którym rekurencja się kończy, a funkcja zaczyna zwracać wartości. W drzewie rekurencji węzły reprezentujące przypadek podstawowy są zwykle przedstawiane jako węzły-liście, ponieważ nie powodują dalszych wywołań rekurencyjnych.

Nieprzezroczystość przejścia CSS

Połączenia rekurencyjne

Węzły podrzędne w drzewie rekurencji reprezentują wywołania rekurencyjne wykonane w ramach funkcji. Każdy węzeł podrzędny odpowiada oddzielnemu wywołaniu rekurencyjnemu, co skutkuje utworzeniem nowych podproblemów. Wartości lub parametry przekazywane do tych wywołań rekurencyjnych mogą się różnić, co prowadzi do zmian w charakterystyce problemów podrzędnych.

Przebieg wykonania:

Przechodzenie przez drzewo rekurencji zapewnia wgląd w przebieg wykonywania funkcji rekurencyjnej. Zaczynając od początkowego wywołania w węźle głównym, podążamy za gałęziami, aby dotrzeć do kolejnych wywołań, aż napotkamy przypadek podstawowy. Po osiągnięciu przypadków podstawowych wywołania rekurencyjne zaczynają powracać, a odpowiadające im węzły w drzewie są oznaczane zwróconymi wartościami. Przechodzenie trwa do momentu przejścia całego drzewa.

Analiza złożoności czasu

Drzewa rekurencji pomagają w analizie złożoności czasowej algorytmów rekurencyjnych. Badając strukturę drzewa, możemy określić liczbę wykonanych wywołań rekurencyjnych i pracę wykonaną na każdym poziomie. Analiza ta pomaga w zrozumieniu ogólnej wydajności algorytmu i zidentyfikowaniu wszelkich potencjalnych nieefektywności lub możliwości optymalizacji.

Wstęp

• Pomyśl o programie wyznaczającym silnię liczby. Ta funkcja przyjmuje na wejściu liczbę N i w rezultacie zwraca silnię N. Pseudokod tej funkcji będzie przypominał,

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Przykładem rekurencji jest wspomniana wcześniej funkcja. Wywołujemy funkcję w celu określenia silni liczby. Następnie, biorąc pod uwagę mniejszą wartość tej samej liczby, funkcja ta wywołuje samą siebie. Trwa to aż do osiągnięcia podstawowego przypadku, w którym nie ma już żadnych wywołań funkcji.
• Rekurencja to technika rozwiązywania skomplikowanych problemów, gdy wynik zależy od wyników mniejszych instancji tego samego problemu.
• Jeśli myślimy o funkcjach, mówimy, że funkcja jest rekurencyjna, jeśli wywołuje samą siebie, aż osiągnie przypadek podstawowy.
• Każda funkcja rekurencyjna ma dwa podstawowe elementy: przypadek podstawowy i krok rekurencyjny. Po dotarciu do przypadku podstawowego przestajemy przechodzić do fazy rekurencyjnej. Aby zapobiec niekończącej się rekurencji, przypadki podstawowe muszą być odpowiednio zdefiniowane i mają kluczowe znaczenie. Definicja nieskończonej rekurencji to rekurencja, która nigdy nie osiąga przypadku podstawowego. Jeśli program nigdy nie osiągnie przypadku podstawowego, przepełnienie stosu będzie nadal występować.

Typy rekurencji

Ogólnie rzecz biorąc, istnieją dwie różne formy rekurencji:

• Rekurencja liniowa
• Rekurencja drzewa
• Rekurencja liniowa

Rekurencja liniowa

• Funkcja, która wywołuje samą siebie tylko raz przy każdym wykonaniu, nazywana jest liniowo rekurencyjną. Dobrą ilustracją rekurencji liniowej jest funkcja silni. Nazwa „rekurencja liniowa” odnosi się do faktu, że wykonanie funkcji rekursywnej liniowo zajmuje liniową ilość czasu.
• Spójrz na poniższy pseudokod:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Jeśli spojrzymy na funkcję doSomething(n), akceptuje ona parametr o nazwie n i wykonuje pewne obliczenia przed ponownym wywołaniem tej samej procedury, ale z niższymi wartościami.
• Kiedy wywoływana jest metoda doSomething() z wartością argumentu n, załóżmy, że T(n) reprezentuje całkowitą ilość czasu potrzebną do zakończenia obliczeń. W tym celu możemy również sformułować relację powtarzania, T(n) = T(n-1) + K. K służy tutaj jako stała. Uwzględniono stałą K, ponieważ przydzielenie lub zwolnienie pamięci dla zmiennej lub wykonanie operacji matematycznej wymaga czasu. Do określenia czasu używamy K, ponieważ jest on tak minutowy i nieistotny.
• Złożoność czasową tego programu rekurencyjnego można w prosty sposób obliczyć, ponieważ w najgorszym scenariuszu metoda doSomething() jest wywoływana n razy. Formalnie rzecz biorąc, złożoność czasowa funkcji wynosi O(N).

Rekurencja drzewa

• Kiedy w przypadku rekurencyjnym wykonujesz wywołanie rekurencyjne więcej niż raz, nazywa się to rekursją drzewa. Skuteczną ilustracją rekurencji drzewa jest ciąg Fibonacciego. Funkcje rekurencyjne drzewa działają w czasie wykładniczym; nie są liniowe w swojej czasowej złożoności.
• Spójrz na poniższy pseudokod,

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Jedyna różnica między tym kodem a poprzednim polega na tym, że ten wykonuje jeszcze jedno wywołanie tej samej funkcji z niższą wartością n.
• Przyjmijmy T(n) = T(n-1) + T(n-2) + k jako relację powtarzania dla tej funkcji. K ponownie służy jako stała.
• Kiedy wykonywane jest więcej niż jedno wywołanie tej samej funkcji z mniejszymi wartościami, ten rodzaj rekurencji nazywany jest rekursją drzewa. Intrygującym aspektem jest teraz: jak czasochłonna jest ta funkcja?
• Zgadnij na podstawie poniższego drzewa rekurencji dla tej samej funkcji.
  
• Może się zdarzyć, że oszacowanie złożoności czasowej na podstawie bezpośredniego spojrzenia na funkcję rekurencyjną jest trudne, szczególnie gdy jest to rekurencja drzewiasta. Metoda drzewa rekurencji jest jedną z kilku technik obliczania złożoności czasowej takich funkcji. Przeanalizujmy to bardziej szczegółowo.

Co to jest metoda drzewa rekurencji?

• Relacje powtarzania, takie jak T(N) = T(N/2) + N lub dwie, które omówiliśmy wcześniej w sekcji poświęconej rodzajom rekurencji, są rozwiązywane przy użyciu podejścia drzewa rekurencji. Te relacje powtarzalności często wykorzystują strategię „dziel i zwyciężaj”, aby rozwiązać problemy.
• Integracja odpowiedzi na mniejsze podproblemy, które powstają, gdy większy problem jest dzielony na mniejsze, wymaga czasu.
• Na przykład relacja powtarzania wynosi T(N) = 2 * T(N/2) + O(N) dla sortowania przez scalanie. Czas potrzebny na połączenie odpowiedzi na dwa podproblemy o łącznej wielkości T(N/2) wynosi O(N), co jest prawdą również na poziomie implementacji.
• Na przykład, ponieważ relacja powtarzalności dla wyszukiwania binarnego to T(N) = T(N/2) + 1, wiemy, że każda iteracja wyszukiwania binarnego daje w wyniku przestrzeń poszukiwań przeciętą o połowę. Po ustaleniu wyniku wychodzimy z funkcji. Do relacji powtarzania dodano +1, ponieważ jest to operacja na stałym czasie.
• Należy wziąć pod uwagę relację powtarzania T(n) = 2T(n/2) + Kn. Kn oznacza ilość czasu potrzebną do połączenia odpowiedzi na podproblemy n/2-wymiarowe.
• Przedstawmy drzewo rekurencji dla wspomnianej relacji rekurencji.

Z analizy powyższego drzewa rekurencji możemy wyciągnąć kilka wniosków, w tym

1. Przy określaniu wartości węzła liczy się jedynie wielkość problemu na każdym poziomie. Wielkość emisji wynosi n na poziomie 0, n/2 na poziomie 1, n/2 na poziomie 2 i tak dalej.

2. Generalnie wysokość drzewa definiujemy jako równą log (n), gdzie n jest wielkością problemu, a wysokość tego drzewa rekurencji jest równa liczbie poziomów w drzewie. Jest to prawdą, ponieważ, jak właśnie ustaliliśmy, strategia dziel i zwyciężaj jest wykorzystywana do rozwiązywania problemów w oparciu o relacje powtarzania, a przejście od problemu o rozmiarze n do problemu o rozmiarze 1 wymaga po prostu wykonania log(n) kroków.

• Rozważmy na przykład wartość N = 16. Jeśli w każdym kroku możemy podzielić N przez 2, ile kroków potrzeba, aby otrzymać N = 1? Biorąc pod uwagę, że w każdym kroku dzielimy przez dwa, poprawną odpowiedzią jest 4, co stanowi wartość log(16) o podstawie 2.

log(16) podstawa 2

log(2^4) podstawa 2

4 * log(2) o podstawie 2, ponieważ log(a) o podstawie a = 1

więc 4 * log(2) podstawa 2 = 4

3. Na każdym poziomie drugi człon nawrotu uważany jest za pierwiastek.

Chociaż w nazwie tej strategii pojawia się słowo „drzewo”, nie trzeba być ekspertem od drzew, aby ją zrozumieć.

Jak używać drzewa rekurencji do rozwiązywania relacji powtarzania?

Koszt podproblemu w technice drzewa rekurencji to ilość czasu potrzebna do rozwiązania podproblemu. Dlatego też, jeśli zauważysz wyrażenie „koszt” powiązane z drzewem rekurencji, odnosi się ono po prostu do ilości czasu potrzebnego do rozwiązania określonego problemu cząstkowego.

hiba bukhari

Rozumiemy wszystkie te kroki na kilku przykładach.

Przykład

Rozważ relację powtarzania,

T(n) = 2T(n/2) + K

Rozwiązanie

Podana relacja powtarzania ma następujące właściwości,

Problem o rozmiarze n jest podzielony na dwa podproblemy, każdy o rozmiarze n/2. Koszt łączenia rozwiązań tych podproblemów wynosi K.

Każdy problem o rozmiarze n/2 jest podzielony na dwa podproblemy, każdy o rozmiarze n/4 i tak dalej.

Na ostatnim poziomie rozmiar podproblemu zostanie zmniejszony do 1. Innymi słowy, w końcu trafiliśmy na przypadek podstawowy.

Postępujmy zgodnie z instrukcjami, aby rozwiązać tę relację powtarzania,

Krok 1: Narysuj drzewo rekurencji

wyrażenie regresji w Javie

Krok 2: Oblicz wysokość drzewa

Ponieważ wiemy, że gdy stale dzielimy liczbę przez 2, przychodzi moment, gdy liczba ta zostaje zmniejszona do 1. Podobnie jak w przypadku problemu o rozmiarze N, załóżmy, że po K podzieleniu przez 2 N staje się równe 1, co oznacza, ( n/2^k) = 1

Tutaj n/2^k jest rozmiarem problemu na ostatnim poziomie i zawsze jest równy 1.

Teraz możemy łatwo obliczyć wartość k z powyższego wyrażenia, przenosząc log() na obie strony. Poniżej znajduje się bardziej przejrzyste wyprowadzenie,

testowanie i typy oprogramowania

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) o podstawie 2

Zatem wysokość drzewa wynosi log(n) o podstawie 2.

Krok 3: Oblicz koszt na każdym poziomie

• Koszt na poziomie 0 = K, dwa podproblemy są łączone.
• Koszt na poziomie 1 = K + K = 2*K, dwa podproblemy są łączone dwukrotnie.
• Koszt na poziomie 2 = K + K + K + K = 4*K, dwa podproblemy są łączone czterokrotnie. i tak dalej....

Krok 4: Oblicz liczbę węzłów na każdym poziomie

Najpierw określmy liczbę węzłów na ostatnim poziomie. Z drzewa rekurencji możemy to wywnioskować

• Poziom 0 ma 1 (2^0) węzeł
• Poziom 1 ma 2 (2^1) węzły
• Poziom 2 ma 4 (2^2) węzły
• Poziom 3 ma 8 (2^3) węzłów

Zatem poziom log(n) powinien mieć 2^(log(n)) węzłów, tj. n węzłów.

Krok 5: Podsumuj koszt wszystkich poziomów

• Całkowity koszt można zapisać jako:
• Koszt całkowity = Koszt wszystkich poziomów z wyjątkiem ostatniego poziomu + Koszt ostatniego poziomu
• Koszt całkowity = Koszt poziomu-0 + Koszt poziomu-1 + Koszt poziomu-2 +.... + Koszt poziomu-log(n) + Koszt ostatniego poziomu

Koszt ostatniego poziomu oblicza się osobno, ponieważ jest to przypadek bazowy i na ostatnim poziomie nie dokonuje się łączenia, więc koszt rozwiązania pojedynczego problemu na tym poziomie ma pewną stałą wartość. Przyjmijmy to jako O (1).

Umieśćmy wartości we wzorach,

• T(n) = K + 2*K + 4*K + .... + log(n)` razy + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) razy)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) razy + O(n)

Jeśli przyjrzysz się uważnie powyższemu wyrażeniu, tworzy ono postęp geometryczny (a, ar, ar^2, ar^3 ...... czas nieskończony). Sumę GP wyraża się wzorem S(N) = a / (r - 1). Oto pierwszy wyraz, a r jest wspólnym stosunkiem.