DOUG LLOYD: Jeśli widzieliście wideo na rekursji, cały proces może mieć Wydawało się trochę magiczne. Jak to działa? Jak funkcje wiedzieć, że trzeba czekać i czekać na inną wartość powrócić z inną funkcją zadzwonić, aby uzyskać wynik chcemy? Cóż, powód to działa to, ponieważ czegoś znanego jako stos wywołań. Kiedy zadzwonić do funkcji, System rezerwuje miejsca w pamięci dla tej funkcji, aby wykonać swoją pracę. A my nazywamy te fragmenty pamięci, które odłogowania są dla każdej funkcji wywołać ramkę stosu lub ramkę funkcji. I jak można się spodziewać, te ramki stosu Mieszkam na części stosu pamięci. 

Więcej niż jedna funkcja stosu ramki może występować w pamięci w danym czasie. Jeśli głównym wywołuje ruch funkcji, i ruch nazywa kierunek, Wszystkie trzy funkcje mają otwarte ramki. Ale nie wszyscy mają aktywnych ramek. Ramy te są ułożone w stos. I rama z ostatnio się Funkcja ta jest zawsze na górze stosu. I to jest zawsze aktywna ramka. Jest tylko jeden naprawdę kiedykolwiek aktywna funkcja to na raz. Jest to jeden na górze stosu. 

Gdy funkcja wymaga innego Funkcja, to jakby naciska pauzę. To rodzaj jest zawieszone, czekając. I kolejna ramka stosu jest wciśnięty na stos na wierzchu. I to staje się aktywna ramka. I rama natychmiast Poniżej musi czekać dopóki nie jest jeszcze aktywna ramka zanim będzie mógł wznowić swoje prace. Kiedy funkcja jest kompletne i gotowe, jego rama jest zdejmowana ze stosu. To jest terminologia. I rama natychmiast pod nim, jak już powiedziałem, staje się nową aktywną ramkę. 

A jeśli wywołuje inną funkcję, to się jeszcze wstrzymać. Stack frame, że nowa funkcja będzie zostać przesunięta na górze stosu. To zrobi swoją pracę. To może pop wycofać. A druga funkcja Poniżej można go wznowić. 

Warto więc przejść przez to jeszcze raz, patrząc na myśl o funkcji silni że zdefiniowane w rekurencja video, dokładnie, jak magia za tym Proces odbywa rekurencyjne. Więc to jest nasz cały plik, tak? Mamy zdefiniowane dwa functions-- głównym i fakt. I jak można się spodziewać, każdy program C będzie aby rozpocząć w pierwszej linii głównej. 

Więc utworzyć nową ramkę stosu dla Głównym. I to będzie się ukazywać. Główne połączenia printf. I printf będzie wydrukować silni 5. Cóż, nie wiem, silnia z 5, co jest, i tak to wezwanie jest już w zależności od innego wywołania funkcji. Tak więc głównym będzie wstrzymać tam. Zamierzam zostawić jej strzałka w prawo tam, kolor to ten sam kolor, jak stos ramki po prawej stronie, co oznacza, że ​​główny ma zamrożenia tutaj natomiast silnia 5 nazywa. 

Więc silnia 5 nazywa. I to będzie rozpocząć się bardzo począwszy od funkcji silni. To zadaje pytanie mam równa 1? 5 jest równa 1? Nie dobrze. Więc to będzie zejść do else część, powrót n razy silnia n minus 1. No, OK. 

Więc teraz, silnia 5 jest w zależności od innego połączenia do czynnikowych, przechodząc w 4 jako parametru. I tak silnia 5 ramka, że ​​czerwoną ramką, zamierza zamrozić tam w tym wierszu Mam wskazany i czekać na silni 4 do końca co trzeba zrobić, aby następnie go może stać się ponownie aktywną ramkę. 

Tak silni 4 startów w początek silnia. Czy 4 równe 1? Nie, tak to będzie to samo. To będzie zejść z innego oddziału. To będzie dostać się do tej linii kodu. OK, mam zamiar wrócić cztery razy. Och, silnia 3-- tak silni 4 zależy od silni 3 wykończenia. 

A więc musi zadzwonić silni 3. I to będzie przejść przez Ten sam proces ponownie. Zaczyna poprzez, dostaje tutaj. Silnia 3 zależy na silni 1. Więc silnia 2 startów, dostaje tutaj. To zależy od silni 1. Silnia 1 startów. 

OK. Więc teraz, że jesteśmy coraz gdzieś ciekawe, prawda? Teraz, 1 oznacza liczbę 1. I tak wracamy 1. W tym momencie wracamy. Funkcja zrobić. To zachowanie jest-- tam nic innego nie robić, i tak ramka stosu dla silnia 1 pojawia się. Jest skonczone. Powrócił 1. A teraz, silnia 2, które Rama była natychmiast pod nim w stosie, staje się aktywnym ramki. 

I może odebrać dokładnie, w którym zostało przerwane. To już czeka na silni od 1 do zakończenia prac. Obecnie zakończył. I tak oto jesteśmy. 

Silnia 1 wrócił wartość 1. Więc silnia 2 puszki powiedzmy powrócić 2 razy 1. Jej praca jest teraz zrobić. To zwróciło 2 do czynnikowych 3, który czekał na niego. Silnia 3 jest górna ramka, aktywna ramka w stosie. I tak to się mówi, dobrze, dobrze, będę powrót 3 razy 2, który jest 6. I mam zamiar dać, że wartość z powrotem do silnia 4, który został na mnie czeka. Mam dość. Silnia 3 schodzi ze stosu, a silnia 4 jest teraz aktywna ramka. 

4 mówi, OK, mam zamiar wrócić 4 razy silnia 3, co było sześć. To było od wartości, które silnia 3 wrócił. I tak 4 razy 6 jest 24. I mam zamiar przejść że powrót do czynnikowych 5, który został na mnie czeka. Silnia 5 jest teraz aktywna ramka. To będzie powrót 5 razy silnia 4-- 5 razy 24 lub 120-- i podać tę wartość Powrót do głównej, która ma czekali cierpliwie dla długi czas na dole stosu. 

To gdzie to się zaczęło. Wykonana jest to wezwanie. Kilka ramek przejął na górze. Jest teraz z powrotem w górnej części stosu. Jest to aktywna ramka. Tak więc głównym ma wartość 120 z powrotem z silni 5. To już czeka na wydrukować tę wartość. I wtedy to się robi. Nie ma więcej linii kodu w głównym. Tak więc głównym pojawi się ramka użytkownika stos, i gotowe. 

I to jest, jak działa rekurencji. Tak właśnie działa ramki stosu. Te wywołania funkcji to się stało wcześniej to tylko na przerwie czeka dla kolejnych połączeń do końca, dzięki czemu stają się one aktywne kadrowanie i dokończyć to, co trzeba zrobić. 

Jestem Doug Lloyd. To CS50.