Rekurencja jest procesem definiowania problemu (lub rozwiązania problemu) w kategoriach (prostszej wersji) samego.

na przykład, możemy zdefiniować operację „znajdź swoją drogę do domu” jako:

  1. Jeśli jesteś w domu, przestań się ruszać.

  2. zrób krok w stronę domu.

  3. „znajdź drogę do domu”.

tutaj rozwiązanie do znalezienia drogi do domu to dwa kroki (trzy kroki). Po pierwsze, nie wracamy do domu, jeśli już jesteśmy w domu., Po drugie, wykonujemy bardzo proste działanie, które sprawia, że nasza sytuacja jest łatwiejsza do rozwiązania. W końcu ponawiamy cały algorytm.

powyższy przykład nazywa się rekurencją ogonową. Tutaj ostatnie polecenie wywołuje algorytm rekurencyjny. Rekurencję ogonową można bezpośrednio przetłumaczyć na pętle.

Jak napisać rekurencyjny „algorytm” znajdowania kwadratu świątyni?

Innym przykładem rekurencji byłoby znalezienie maksymalnej wartości na liście liczb. Maksymalna wartość na liście to albo pierwsza liczba, albo największa z pozostałych liczb., W ten sposób zapisujemy pseudokod algorytmu:

części algorytmu rekurencyjnego

wszystkie algorytmy rekurencyjne muszą mieć następujące wartości:

  1. wielkość liter bazowych (tzn. kiedy się zatrzymać)

  2. wielkość liter bazowych (tzn. kiedy się zatrzymać)

  3. wywołanie rekurencyjne (tzn. wywołanie siebie)

„work towards Base Case” to miejsce, w którym upraszczamy problem (np. dzielimy listę na dwie części, Każda mniejsza od oryginału). Wywołanie rekursywne, gdzie używamy tego samego algorytmu do rozwiązania prostszej wersji problemu., Przypadek podstawowy jest rozwiązaniem „najprostszego” możliwego problemu (na przykład przypadek podstawowy w problemie „znajdź największą liczbę na liście” byłby taki, gdyby lista miała tylko jeden numer… i z definicji, jeśli jest tylko jedna liczba, jest największa).

prosty przykład: dodaj trzy liczby

dodanie trzech liczb jest równoznaczne z dodaniem pierwszych dwóch liczb, a następnie ponownym dodaniem tych dwóch liczb.

(zauważ, że w Matlab funkcja może być wywołana bez wszystkich argumentów. Funkcja nargin informuje komputer, ile wartości zostało określonych., Tak więc add_numbers(1) będzie miał nargin równy 1; add_numbers(1,1) będzie miał nargin równy 2; add_numbers(1,1,1) będzie miał nargin równy 3.)

Zidentyfikuj 3 części algorytmu rekurencyjnego:

wszystkie algorytmy rekurencyjne muszą mieć następujące trzy etapy:

dlaczego Rekurencja działa

w algorytmie rekurencyjnym komputer „zapamiętuje” każdy poprzedni stan problemu. Informacja ta jest „przechowywana” przez komputer na „stosie aktywacyjnym” (tzn. wewnątrz każdego obszaru roboczego funkcji).

każda funkcja ma swój własny obszar roboczy na każde wywołanie funkcji.,

przykład labiryntu:

rozważ prostokątną siatkę pomieszczeń, w której każdy pokój może mieć lub nie mieć drzwi od strony północnej, południowej, wschodniej i zachodniej.

Jak znaleźć wyjście z labiryntu? Oto jeden z możliwych „algorytmów” do znalezienia odpowiedzi:

dla każdego drzwi w obecnym pokoju, jeśli drzwi prowadzą do wyjścia, weź te drzwi.

„sztuczka” tutaj jest oczywiście, skąd wiemy, czy drzwi prowadzą do pokoju, który prowadzi do wyjścia? Odpowiedź jest taka, że nie wiemy, ale możemy pozwolić komputerowi to wymyślić.

czym jest rekurencyjna część powyższego algorytmu?, To „drzwi prowadzą z labiryntu”. Skąd mamy wiedzieć, czy drzwi prowadzą z labiryntu? Wiemy, bo w pokoju obok (przechodząc przez drzwi) zadajemy to samo pytanie, Jak wyjść z labiryntu?

to, co się dzieje, to komputer „zapamiętuje” wszystkie „to, co jest”. Co jeśli wezmę pierwsze drzwi, co jeśli wezmę drugie drzwi, co jeśli wezmę następne drzwi itp. I dla każdego możliwego drzwi można przejść, komputer zapamiętuje te, co ifs, i dla każdego drzwi po tym, i po tym, itp, aż do końca znajduje.

poniżej znajduje się implementacja kodu zbliżona do rzeczywistej.,

pytanie: Co to jest przypadek podstawowy powyżej?

odpowiedź: (to było podchwytliwe pytanie) w kodzie nie ma liter podstawowych. Musisz sprawdzić na początku, czy pokój jest wyjściem. Jeśli tak, to nie ma rekurencji! 

  function success = find_way_out( maze, room ) if room is exit → return true room ← mark as visited % rest of code ... end

pytanie: jak oznaczyć pokój jako odwiedzony?

odpowiedź: istnieją różne techniki. Jeśli pokój jest strukturą (lub obiektem), możesz dodać do niego odwiedzane pole. (np. pokój.visited = true;) Jeśli nie używasz obiektów, możesz mieć macierz FLAG boolean, która ma ten sam rozmiar/kształt co labirynt i używać tych wartości.,

pytanie: czy są inne problemy z powyższym algorytmem?

odpowiedź: odpowiedź na to pytanie można znaleźć, zastanawiając się nad następującym pytaniem: co by się stało, gdyby labirynt był gigantyczną siatką prostokątnych pomieszczeń o identycznej wielkości, z drzwiami na każdej ścianie? Wyobraź sobie, że idziesz na północ przez pierwsze drzwi, potem na wschód przez następne drzwi, potem na południe przez te drzwi, a potem na zachód przez te drzwi. Gdzie skończyłeś? Tam, gdzie zacząłeś! Co gorsza, możesz kontynuować tę pętlę na zawsze. Jak nieustraszony poszukiwacz przygód rozwiązałby ten problem?,

jedną z odpowiedzi na to jest użycie kawałka kredy i Umieszczenie Dużego X na podłodze każdego pokoju, do którego wchodzicie. Tak więc, kiedy wracasz do pokoju z X na podłodze, wiesz, że nie musisz wchodzić. W przypadku programu należy użyć flagi logicznej „seen” lub „visited”. Każdy pokój ma flagę. Każdy pokój zaczyna się od ustawienia flagi na false. Kiedy odwiedzasz pokój, ustawiasz flagę na true., Wreszcie, w” przypadku podstawowym ” masz wiersz taki jak: 

  function success = find_way_out( maze, room ) % exit chack if room is visited → return false % rest of code ... end

Rekurencja może być równie dobrze zastosowana do algorytmów komputerowych:

niektóre przykłady związane z komputerem obejmują: dodawanie listy liczb, Obliczanie ciągu Fibonacciego, obliczanie czynnika i Sudoku.

pętle i Rekurencja ogonowa

niektóre algorytmy rekurencyjne są bardzo podobne do pętli. Algorytmy te nazywane są „rekurencyjnymi”, ponieważ ostatnią Instrukcją w algorytmie jest „ponowne uruchomienie” algorytmu. Algorytmy rekurencyjne ogonowe mogą być bezpośrednio tłumaczone na pętle.