[MUZYKI] 

DOUG LLOYD: Pewnie myślisz, że Kod jest tylko używane do wykonania zadania. Możesz napisać go. To coś robi. To dość dużo. 

Go skompilować. Uruchomieniu programu. Jesteś dobry, aby przejść. 

Ale wierzcie lub nie, jeśli kodować przez dłuższy czas, rzeczywiście może przyjść, aby zobaczyć Kod jako coś, co jest piękne. Rozwiązuje problem bardzo ciekawy sposób, czy jest coś naprawdę schludny temat jej wyglądu. Można się śmiać na mnie, ale to prawda. I rekurencja jest jeden sposób, do sortowania się ten pomysł z pięknym, eleganckim wyglądzie kod. Rozwiązuje to problem w taki sposób, aby są ciekawe, łatwe do wizualizacji, i zaskakująco krótka. 

Prace sposób rekurencja jest rekurencyjna funkcja jest określona jako funkcja, która wywołuje Sam w ramach jego realizacji. To może wydawać się trochę dziwne, i zobaczymy trochę o tym, jak to działa w jednej chwili. Ale znowu, te procedury rekurencyjne są będzie tak eleganckie bo będą rozwiązać ten problem bez mając te wszystkie inne funkcje lub te długie pętle. Zobaczysz, że to rekurencyjny Procedury będą wyglądać tak krótko. A tak naprawdę idą do Twój kod wyglądać o wiele piękniej. 

Dam ci przykład tego, w jaki sposób procedura rekurencyjna może być zdefiniowana. Więc jeśli jesteś obeznany z tym z lekcji matematyki wiele lat temu, Jest coś, co nazywa się Funkcja silni, która jest zwykle oznaczany jako wykrzyknikiem, który jest określona w stosunku do wszystkich dodatnich liczb całkowitych. A sposób, że n silnia jest obliczana jest pomnożyć wszystkie liczby poniżej lub równą n together-- wszystkie liczby całkowite mniej niż lub równą n razem. 

Więc 5 silnia jest 5 razy 4 razy 3 razy 2 razy 1. I 4 silnia jest 4 razy 3, 2 razy po 1 i tak dalej. Masz pomysł. 

Jako programiści, my nie używać n, wykrzyknik. Będziemy więc zdefiniować silnia Funkcja jako fakt n. I użyjemy silni, aby utworzyć rekurencyjny rozwiązanie problemu. I myślę, że może się okazać, że jest to dużo bardziej wizualnie atrakcyjne niż iteracyjny Wersja ta, Będziemy również przyjrzeć się w jednej chwili. 

Więc oto kilka facts-- pun intended-- o factorial-- silnia funkcji. Silnia 1, jak powiedziałem, to 1. Silnia 2 jest 2 razy 1. Silnia 3 wynosi 3 razy 2 razy po 1 i tak dalej. Rozmawialiśmy o 4 i 5 już. 

Ale patrząc na to, nie jest to prawda? Nie jest silnia 2 tylko 2 razy silnia 1? To znaczy, silnia 1 to 1. Więc dlaczego nie możemy po prostu powiedzieć, że, od silnia 2 jest 2 razy 1, to naprawdę tylko 2 razy silnia 1? 

A następnie rozszerzenie tego pojęcia, nie jest silnia 3 tylko 3 razy silnia 2? I silnia 4 jest 4 razy silnia 3, i tak dalej? W rzeczywistości, silnia z dowolnej liczby można po prostu być wyrażona, jeśli my niby od przeprowadzenia tego na zawsze. Możemy rodzaj uogólnienia silnia problemem jak to n razy silnia n minus 1. To N razy produktem wszystkie numery mniej niż mnie. 

Ten pomysł, to uogólnienie problemu, Pozwala nam to rekurencyjnie zdefiniować funkcję silni. Podczas definiowania funkcji rekurencyjnie, nie Dwie rzeczy, które muszą być jego częścią. Trzeba mieć coś nazywa się wariant podstawowy, który, kiedy wyzwolić go, zatrzyma proces rekurencyjny. 

W przeciwnym razie funkcja, która zwraca itself-- jak można imagine-- może trwać wiecznie. Funkcja wywołuje funkcję wzywa do wywołania funkcji funkcja wywołuje funkcję. Jeśli nie ma sposobu go zatrzymać, program będzie skutecznie zatrzymany w nieskończonej pętli. Zawiesisz w końcu, ponieważ będzie to zabraknie pamięci. Ale, że o to chodzi. 

Musimy mieć jakiś inny sposób, aby zatrzymać rzeczy oprócz naszego programu upaść, ponieważ program, który zawiesza się Prawdopodobnie nie piękne i eleganckie. I tak nazywamy to wariant podstawowy. Jest to proste rozwiązanie do problemu, który zatrzymuje Proces rekurencyjne występowaniu. Więc to jest jedna część Funkcja rekurencyjna. 

Druga część jest rekurencyjna przypadek. I to jest, gdzie rekurencji ten rzeczywiście nastąpi. To jest, gdy Funkcja będzie nazywać się. 

To nie będzie nazywać się w dokładnie taki sam sposób, w jaki został powołany. To będzie niewielkie zmiany sprawia, że ​​problem jest to próbuje rozwiązać malusieńki nieco mniejsze. Ale na ogół przechodzi złotówki rozwiązując masę roztworu do innego połączenia w dół. 

Który z tych strojów jak przypadku bazowego tutaj? Który z nich wygląda jak Najprostsze rozwiązanie problemu? Mamy kilka silni, i mogliśmy kontynuować dzieje on-- 6, 7, 8, 9, 10, i tak dalej. 

Ale jeden z nich wygląda jak Dobrym przykładem będzie wariant podstawowy. To bardzo proste rozwiązanie. Nie musimy robić nic szczególnego. 

Silnia 1 jest tylko jeden. Nie mamy zrobić dowolny Mnożenie w ogóle. Wydaje się, że jeśli mamy aby spróbować rozwiązać ten problem, i musimy się zatrzymać Rekurencja gdzieś, prawdopodobnie chce się zatrzymać że gdy mamy do 1. Nie chcemy, aby zatrzymać przed tym. 

Więc jeśli mamy definiowania nasza funkcja silnia, oto szkielet dla w jaki sposób możemy to zrobić. Musimy podłączyć tych dwóch things-- wariant podstawowy, a rekurencyjne przypadek. Co znajduje się wariant podstawowy? Jeśli n jest równe 1, to powrót 1-- bardzo prosty do rozwiązania problemem. 

Silnia 1 to 1. To nie 1 razy cokolwiek. To tylko jeden. To bardzo łatwe fakt. I tak, że może być naszym wariant podstawowy. Jeśli przejdzie 1 do tego Funkcja, po prostu zwraca 1. 

Jaka jest rekurencyjna Sprawa prawdopodobnie wyglądać? Dla każdego innego numeru oprócz 1, co jest wzór? Cóż, jeśli bierzemy silnia n, To n razy silnia n minus 1. 

Jeśli bierzemy silni 3, to 3 razy silnia 3 minus 1, lub 2. I tak, jeśli nie jesteśmy patrząc na 1, w przeciwnym wypadku powrót n razy silnia n minus 1. To całkiem proste. 

I w imię konieczności nieznacznie czystsze i bardziej Kod elegancki, wiedzą, że jeśli mamy pętle jednoliniowy lub jednoliniowy skoków warunkowych, możemy pozbyć wszystkie z nawiasy klamrowe wokół nich. Więc możemy skonsolidować to do tego. To jest dokładnie to samo funkcjonalność jak ten. 

Ja tylko odbierając kręcone szelki, bo jest tylko jedna linia wewnątrz tych oddziałów warunkowych. Więc te zachowują się identycznie. Jeśli n jest równe 1, powrót 1. W przeciwnym razie zwraca n razy silnia n minus 1. Więc robimy problem mniejszy. Jeśli n zaczyna się jak 5, będziemy powrót 5 razy silni 4. I zobaczymy, w chwili, gdy mówimy o stack-- połączeń w innym wideo gdzie mówimy o zadzwoń stack-- dowiemy się o tym, dlaczego działa dokładnie ten proces. 

Ale podczas silnia 5 mówi powrót 5 razy silnia 4 i 4 powie, dobrze, dobrze, powrót 4 razy silnia 3. I jak widać, jesteśmy rodzaj zbliża 1. Jesteśmy coraz bliżej i bliżej tym przypadku bazowego. 

I raz trafiliśmy w sprawę podstawową, wszystkich poprzednich funkcji ma odpowiedzi szukali. Silnia 2 mówił powrót 2 razy silnia 1. Cóż, silnia 1 Zwraca 1. Tak więc wezwanie do silnia z 2 może powrócić 2 razy 1, i daj to z powrotem do silni 3, który czeka na tego wyniku. 

I wtedy można obliczyć jego wynik, 3 razy 2 jest 6, i oddać silni 4. I znowu mamy wideo na stosie wywołań gdzie jest to przedstawione trochę więcej niż to, co mówię teraz. Ale to jest to. Samo to jest rozwiązanie obliczania silni liczby. 

To tylko cztery linie kodu. To bardzo fajne, prawda? To trochę sexy. 

Tak więc w ogólności, lecz nie Zawsze, rekurencyjna funkcja może zastąpić pętli w nierekursywnych funkcji. Więc, obok siebie, jest iteracyjna wersja funkcji silni. Obie te oblicz dokładnie to samo. 

Oboje obliczyć silnię n. Wersja na lewo używa rekursji, aby to zrobić. Wersja na prawo wykorzystuje iteracji, aby to zrobić. 

Oraz informacja, musimy zadeklarować zmienna produktem całkowitą. A potem w pętli. Pod warunkiem, n jest większe niż 0, mamy utrzymać mnożąc ten produkt przez n i zmniejszanie n, aż obliczamy produkt. Tak więc te dwie funkcje, znowu, zrobić dokładnie to samo. Ale nie rób tego w dokładnie tak samo. 

Teraz możliwe jest więcej niż jedną bazę przypadek lub więcej niż jeden rekurencyjne przypadku, w zależności na co twoja funkcja stara się zrobić. Nie zawsze są ograniczone tylko do jeden wariant podstawowy lub pojedynczy rekurencyjne walizka. Więc to przykład czegoś, z wielu przypadków bazowych może być this-- Ciąg liczb Fibonacciego. 

Można przypomnieć od elementarne dni szkolne że sekwencja Fibonacci definiuje jak this-- pierwszy element jest 0. Drugi element 1. Obie z nich są po prostu z definicji. 

Następnie każdy inny element jest zdefiniowany a suma n plus 1, a n minus 2. Więc trzeciego elementu byłoby 0 plus 1 to 1. A potem czwarty element jest drugim elementem, 1, oraz trzeci element 1. A to byłoby 2. I tak dalej, i tak dalej. 

Więc w tym przypadku, mamy dwa przypadki bazowe. Jeśli n jest równe 1, powrót 0. Jeśli n wynosi 2, powrót 1. W przeciwnym razie, powrót Fibonacciego n minus 1 plus Fibonacciego n minus 2. 

Więc to jest kilka przypadków bazowych. Co z wielu cyklicznych przypadkach? Cóż, coś zwana hipoteza Collatz. Nie powiem, Wiesz, co to jest, bo to rzeczywiście nasza ostateczna Problemem dla tego filmu wideo. I to jest nasza ćwiczenia działać wspólnie. 

Więc oto co Collatz domysły jest-- ma zastosowanie do każdej liczby całkowitej dodatniej. I spekuluje, że jest to Zawsze można wrócić do 1, jeśli wykonaj następujące kroki. Jeśli n jest 1, stop. Mamy z powrotem na 1, jeśli n oznacza 1. 

W przeciwnym razie, przejść przez to Proces ponownie n dzieli się przez 2. I sprawdzić, czy można wrócić do 1. W przeciwnym razie, jeśli n jest nieparzyste, przejść proces ten ponownie 3n plus 1, lub 3 razy n plus 1. Więc tutaj mamy jeden przypadek bazowy. Jeśli n jest równe 1, stop. Nie robimy żadnych więcej rekursji. 

Ale mamy dwa rekurencyjne przypadki. Jeśli n jest parzyste, robimy jeden rekurencyjnych Sprawa, nazywając n dzieli się przez 2. Jeśli n jest nieparzyste, robimy różne Przypadek 3 rekurencyjne n razy plus 1. 

A więc celem tego filmu jest wziąć drugi, wstrzymać odtwarzanie pliku wideo, i spróbować napisać to Funkcja rekurencyjna Collatz gdzie przechodzą w wartości n, a oblicza, ile kroków, potrzeba, aby do 1, jeśli zaczniesz od n i wykonaj te kroki się powyżej. Jeśli n oznacza 1, to trwa 0 czynności. W przeciwnym razie, to będzie jeden krok plusa jednak wiele czynności wykonywanych na każdej n podzielony przez 2, gdy n jest równe, albo 3 n plus 1 jeśli n jest nieparzyste. 

Teraz, mam umieścić na ekranie tutaj kilka rzeczy badań dla Ciebie, kilka testów przypadkach dla Ciebie, aby zobaczyć co te są różne numery Collatz, a także ilustracją z kroków, które trzeba przeszedł więc można rodzaj zobaczyć ten proces w akcji. Tak więc, gdy n jest równe 1, Collatz n wynosi 0. Nie musisz robić wszystko, aby wrócić do 1. Jesteś już tam jest. 

Jeśli n oznacza 2, to ma jeden krok, aby dostać się do 1. Zaczynasz z 2. Więc, 2 nie jest równa 1. Więc to będzie jeden krok plus jednak wiele kroków, przybiera n dzieli się przez 2. 

2 podzielone przez 2 to 1. Tak to trwa jeden krok plusa jednak wiele kroków trwa do 1. 1 ma zerowe kroki. 

Na 3, jak widać, nie ma sporo etapów. Idziesz od 3. A następnie udać się do 10, 5, 16, 8, 4, 2, 1. To trwa siedem kroków, aby wrócić do 1. I jak widać, istnieje kilka innych przypadków testowych tutaj przetestować swój program. Więc jeszcze raz, zatrzymać wideo. I pójdę wrócić teraz co sam proces jest tutaj, co to przypuszczenie. 

Sprawdź, czy możesz dowiedzieć się, jak zdefiniować Collatz n tak, że oblicza, ile kroki trzeba, aby dostać się do 1. Więc mam nadzieję, wstrzymaniu wideo i nie czekają na mnie dać odpowiedź tutaj. Ale jeśli jesteś, dobrze, oto odpowiedź tak. 

Więc tutaj jest możliwe określenie funkcji Collatz. Nasza baza case-- jeśli n jest równa 1, to zwraca 0. Nie bierze żadnej kroki, aby wrócić do 1. 

W przeciwnym razie mamy dwa rekurencyjne cases-- jeden dla liczb parzystych i jeden dla dziwne. Sposób, w jaki przetestować liczb parzystych jest sprawdzenie, czy n mod 2 jest równa 0. Jest to w zasadzie, ponownie zadać pytanie, jeśli przypomnieć, co mod jest-- jeśli podział n przez 2 ma tam pozostała? To byłoby liczbą parzystą. 

I tak, jeśli n mod 2 jest równa 0 to Badanie to jest liczbą parzystą. Jeśli tak, chcę wrócić 1, bo to jest na pewno przyjmuje jeden krok do plusa Collatz z co liczba jest połowa mnie. W przeciwnym razie, chcę wrócić 1 plus Collatz z 3 razy n plus 1. To był drugi rekurencyjne krokiem, że może trwać do obliczenia Collatz-- liczbę kroków trzeba, by wrócić do 1 podano numer. Więc mam nadzieję, że ten przykład dał ci trochę o smaku procedur rekurencyjnych. Mamy nadzieję, że myślisz, że kod jest trochę więcej piękna, jeśli realizowane w eleganckim, rekurencyjnego sposób. Ale nawet jeśli nie, rekurencja jest naprawdę potężnym narzędziem, jednak. A więc jest to zdecydowanie coś aby uzyskać głowę, ponieważ będziesz w stanie stworzyć całkiem fajne programy za pomocą rekurencji które mogłyby być złożone do pisania jeśli korzystasz z pętli i iteracji. Jestem Doug Lloyd. To CS50.