>> ZAMYLA: Aby zrozumieć rekurencja, należy
najpierw zrozumieć rekurencję.
Mając rekursji w programie środków projektowych że masz samozwrotny
definicje.
Rekurencyjne struktury danych, na przykład są struktury danych, które
zawierać się w ich definicje.
Ale dziś, mamy zamiar skupić się na funkcji rekurencyjnych.
>> Przypomnijmy, że funkcje się wejść, argumenty i zwraca wartość, jak ich
reprezentowane przez wyjście ten schemat tutaj.
Będziemy myśleć o polu jako ciało Funkcja, zawierający zestaw
instrukcje, które interpretują wejściowego i dostarczania sygnału wyjściowego.
Bliższe spojrzenie wewnątrz ciała Funkcja może ujawnić połączeń do
innych funkcji, jak również.
Weź tę prostą funkcję, Foo, że przyjmuje pojedynczy ciąg na wejściu i
druki ile liter że ciąg ma.
Funkcja strlen, na długości łańcucha, nazywa, którego wyjście jest
wymagane do wywołania printf.
>> Teraz, co sprawia, że ​​funkcji rekurencyjnej szczególną jest to, że nazywa się.
Możemy reprezentować ten Cykliczne zadzwonić z tym Orange
pętli z powrotem do siebie.
Ale wykonanie się znowu będzie tylko dokonać innego wywołanie rekurencyjne, a
drugiego i drugiego.
Ale funkcje rekurencyjne nie może być nieskończony.
Mają do końca jakoś, czy Twój Program będzie trwał wiecznie.
>> Więc musimy znaleźć sposób, aby złamać z połączeń rekurencyjnych.
Nazywamy to wariant podstawowy.
Gdy warunek jest spełniony przypadek bazowy, Funkcja zwraca bez dokonywania
kolejny wywołanie rekurencyjne.
Weź tę funkcję, hi, funkcję void że bierze int n jako wejście.
Baza jest pierwszy przypadek.
Jeśli n jest mniejsza od zera, do widzenia i druku zwrotu dla wszystkich innych przypadkach,
Funkcja drukowania hi i wykonać wywołanie rekurencyjne.
Innym wywołanie funkcji z hi zmniejszana wartość wejściowa.
>> Teraz, mimo że drukowanie hi, funkcja nie zostanie zakończona, dopóki nie
zwraca jego typ zwracany, w tym przypadku pustki.
Tak więc dla każdego n poza przypadku bazowej funkcja ta zwróci hi hi
n minus 1.
Ponieważ ta funkcja jest nieaktualna chociaż, my Nie będzie tu wyraźnie wpisać zwrot.
Musimy tylko wykonać funkcję.
Więc dzwoni hi (3) i będą drukowane hi wykonać cześć (2), który wykonuje hi (1) jeden
który realizuje hi (0), gdzie Stan przypadek bazowy jest spełniony.
Więc cześć (0) drukuje do widzenia i wraca.
>> OK.
Więc teraz, że mamy zrozumieć podstawy rekurencyjne funkcje, które są potrzebne
w co najmniej jednym przypadku bazy, jak również wywołanie rekurencyjne, przejdźmy do
bardziej znaczący przykład.
Jeden, który nie tylko powrót unieważnić nie wiem co.
>> Rzućmy okiem na silnia Operacja stosowane najczęściej w
obliczenia prawdopodobieństwa.
Silnia n jest iloczynem co dodatnią liczbę całkowitą mniejszą
a n równe.
Tak silni pięć jest 5 razy 4 razy 3, 2 razy po 1 i otrzymano 120.
Cztery silnia jest 4 razy 3 razy 2 razy 1 otrzymując 24.
I ma zastosowanie ta sama zasada do każdej liczby całkowitej.
>> Więc jak możemy napisać rekurencyjną funkcja, która oblicza silnię
z szeregu?
Cóż, musimy zidentyfikować zarówno wariant podstawowy i wywołanie rekurencyjne.
Wywołanie rekurencyjne będzie taki sam we wszystkich przypadkach, z wyjątkiem podstawy
przypadku, co oznacza, że ​​będziemy musieli znaleźć wzór, który da nam nasze
pożądany wynik.
>> W tym przykładzie, zobacz jak 5 silnia polega na pomnożeniu 4 na 3 przez 2 do 1
I że sam mnożenie stwierdzono tutaj
Definicja 4 silnia.
Widzimy więc, że jest 5 silnia zaledwie 5 razy 4 silnia.
Teraz to ma zastosowanie wzór do 4 czynnikowych, jak również?
Tak.
Widzimy, że zawiera 4 silnia mnożenia 3 razy 2 razy 1,
Ta sama definicja jak 3 silnia.
Tak 4 silnia równa się 4 razy 3 silnia i tak dalej, i tak dalej naszym
kije do 1 wzór, który silnia zgodnie z definicją jest równa 1.
>> Nie ma innego pozytywne liczbami całkowitymi w lewo.
Mamy więc wzór dla nasze wywołanie rekurencyjne.
n silnia równa się n razy silnia n minus 1.
A nasz scenariusz bazowy?
To będzie po prostu nasza definicja 1 silnia.
>> Teraz możemy przejść do pisania kod funkcji.
Dla przypadku bazowego, musimy Stan n równa wynosi 1, gdzie
wrócimy 1.
Następnie przejść na cyklicznej rozmowy wrócimy n razy
silnia n minus 1.
>> Sprawdźmy teraz ten nasz.
Spróbujmy silni 4.
Na naszej funkcji jest równa do 4 razy silnia (3).
Silnia (3) jest równa 3 razy silnia (2).
Silnia (2) jest równy 2 razy silnia (1), która zwraca 1.
Silnia (2) zwraca teraz 2 razy 1, 2.
Silnia (3) może teraz powrócić 3 razy 2, 6.
I wreszcie, silnia (4) zwraca 4 razy 6, 24.
>> Jeśli napotykają żadnych trudności z rekurencyjnego wywołania, udawać, że
funkcja działa już.
Co mam na myśli to, że zalecana ufać swoim rekurencyjnych wywołań, aby powrócić
odpowiednie wartości.
Na przykład, jeśli wiem, że silnia (5) wynosi 5 razy
silnia (4), mam nadzieję, że będzie silnia (4) da mi 24.
Potraktujcie to jako zmienna, jeśli będzie, jak już określono
silnia (4).
Więc dla każdego silnia (n), to Produkt n i
poprzedni silnia.
I ten poprzedni silnia uzyskuje się przez wywołanie
silnia n minus 1.
>> Teraz, czy można wdrożyć rekurencyjne funkcjonować samodzielnie.
Załadować do terminala lub run.cs50.net, i napisz sumę funkcji
że bierze całkowitą n i zwraca suma wszystkich kolejnych pozytywne
liczby całkowite od 1 do n.
Pisałem z niektórych kwot Wartości, które pomogą Ci nasza.
Po pierwsze, dowiedzieć się, Stan przypadek bazowy.
Następnie spojrzeć na sumy (5).
Można wyrazić w kategoriach innej sumy?
Teraz, co z sumy (4)?
Jak możesz wyrazić sumę (4) względem innej sumy?
>> Gdy masz sumę (5) i suma (4) wyrażone w innych sum patrz
Jeśli można zidentyfikować wzór na sumę (n).
Jeśli nie, spróbuj kilka innych numerów i wyrazić swoje sumy w
terminy kolejnych numerów.
Poprzez określenie wzorów dla dyskretnych numery, jesteś na dobrej drodze do
identyfikujący wzorzec dla każdego n.
>> Rekurencja jest bardzo potężnym narzędziem, tak, oczywiście, że nie ogranicza się do
funkcje matematyczne.
Rekurencja może być używany bardzo skutecznie w kontaktach z drzew, na przykład.
Sprawdź mało drzew na bardziej szczegółowy przegląd, ale teraz
Przypomnijmy, że szukanie binarne drzew, w przede wszystkim składa się z węzłów, z których każda
o wartości i dwoma wskaźnikami węzłów.
Zwykle, jest to reprezentowane przez Rodzic mający jeden wiersz wskazujący
do lewego i jednego węzła podrzędnego po prawej węzła podrzędnego.
Struktura poszukiwania binarnego dobrze nadaje się drzewo
do cyklicznej wyszukiwania.
Wywołanie rekurencyjne, albo przechodzi w lewy lub prawy węzeł, ale bardziej
o, że w krótkim drzewa.
>> Powiedzmy, że chcesz, aby wykonać operację na każdy węzeł w binarnym drzewie.
Jak można go o to?
Cóż, można napisać rekurencyjną Funkcja, która wykonuje operację
na węźle nadrzędnym i sprawia rekurencyjną zadzwonić do tej samej funkcji,
przechodzącą w lewo i prawe węzły potomne.
Na przykład, funkcja ta, bla, że zmienia wartość danego węzła i
wszystkie jego dzieci do 1.
Wariant podstawowy z przyczyn węzłów null Funkcja powrotu, wskazując
że nie ma żadnych węzłów w lewo w tym sub-tree.
>> Przejdźmy przez to.
Pierwszy rodzic jest 13.
Zmieniamy wartość na 1, a następnie wywołać Nasza funkcja po lewej stronie, jak również
w prawo.
Funkcja, bla, nazywa się po lewej pierwszy podpotok drzewa, tak lewym węzłem
zostanie przeniesiony do 1 i foo miano na dzieci tego węzła, w
pierwsza w lewo i potem w prawo, i tak dalej, i tak dalej.
I powiedz im, że nie mają oddziałów więcej dzieci, więc sam proces
będzie w dalszym ciągu za prawo dzieci dopóki węzły całego drzewa są
przeniesiony do 1.
>> Jak widać, nie są ograniczone tylko do jednego wywołanie rekurencyjne.
Tylko tyle, ile będzie to zadanie.
Co jeśli miał drzewa, gdzie każdy węzeł miał troje dzieci,
Lewy, środkowy i prawy?
Jak można edytować foo?
Cóż, proste.
Wystarczy dodać kolejne połączenie i rekurencyjnej przechodzą w węzeł środkowy wskaźnika.
>> Rekurencja jest bardzo silny i nie do wspomnieć, elegancki, ale może być
trudne pojęcie na początku, więc być pacjenta i nie spiesz się.
Start z przypadku bazowego.
To zazwyczaj najłatwiej zidentyfikować, i wtedy można pracować
do tyłu stamtąd.
Wiesz, trzeba dotrzeć do wariant podstawowy, tak, że może
dać kilka wskazówek.
Starają się wyrazić w jeden konkretny przypadek Terminy pozostałych przypadkach lub w podzbiorów.
>> Dzięki za oglądanie tego krótkie.
Przynajmniej, teraz możesz rozumieją dowcipy jak ten.
Nazywam się Zamyla, i to jest CS50.
>> Weź tę funkcję, hi, void funkcja, która trwa
int n, jako wejście.
Baza jest pierwszy przypadek.
Jeśli n jest mniejsza niż 0, druk "Do widzenia" i powrót.