1 00:00:00,000 --> 00:00:05,587 2 00:00:05,587 --> 00:00:07,670 DOUG LLOYD: Dacă ați văzut video de pe recursivitate, 3 00:00:07,670 --> 00:00:10,170 întregul proces ar putea avea părea un pic magic. 4 00:00:10,170 --> 00:00:10,930 Cum functioneazã? 5 00:00:10,930 --> 00:00:15,010 Cum funcțiile știu că trebuie să așteptați și să aștepte pentru o altă valoare 6 00:00:15,010 --> 00:00:19,150 pentru a reveni la o funcție diferită apel în scopul de a obține rezultatul ne-o dorim? 7 00:00:19,150 --> 00:00:22,550 >> Ei bine, motivul este pentru că aceasta funcționează de ceva cunoscut sub numele de stiva de apel. 8 00:00:22,550 --> 00:00:26,360 Când apelați un funcție, Sistemul pune deoparte spațiu în memorie 9 00:00:26,360 --> 00:00:28,120 pentru această funcție pentru a face munca sa. 10 00:00:28,120 --> 00:00:31,720 Și numim aceste bucăți de memorie care sunt retrase din circuitul agricol pentru fiecare funcție 11 00:00:31,720 --> 00:00:35,670 apela un cadru stivă sau un cadru funcție. 12 00:00:35,670 --> 00:00:38,290 Și, după cum s-ar putea aștepta, aceste cadre stiva 13 00:00:38,290 --> 00:00:41,000 trăiesc din partea stiva de memorie. 14 00:00:41,000 --> 00:00:43,960 15 00:00:43,960 --> 00:00:47,540 >> Mai mult de o funcție cadru stivă poate exista în memorie la un moment dat. 16 00:00:47,540 --> 00:00:51,240 În cazul în care principala solicită o mișcare funcție, și muta solicită direcție, 17 00:00:51,240 --> 00:00:54,460 toate cele trei funcții au cadre deschise. 18 00:00:54,460 --> 00:00:57,350 Dar nu toți au cadre activi. 19 00:00:57,350 --> 00:00:59,410 Aceste cadre sunt aranjate într-o stivă. 20 00:00:59,410 --> 00:01:01,820 Și a cadrelor din cel mai recent numit 21 00:01:01,820 --> 00:01:04,390 Funcția este întotdeauna pe partea de sus a stivei. 22 00:01:04,390 --> 00:01:07,150 Și care este întotdeauna cadrul activ. 23 00:01:07,150 --> 00:01:10,420 Există doar foarte vreodată funcție care este activă la un moment dat. 24 00:01:10,420 --> 00:01:12,420 Este cea de pe partea de sus a stivei. 25 00:01:12,420 --> 00:01:17,620 >> Când o funcție solicită un alt funcție, ea un fel de prese pauză. 26 00:01:17,620 --> 00:01:20,590 Acesta fel de este în așteptare, de așteptare. 27 00:01:20,590 --> 00:01:24,050 Și un alt cadru stivă este împins pe stiva pe partea de sus a acesteia. 28 00:01:24,050 --> 00:01:26,150 Și care devine cadrul activ. 29 00:01:26,150 --> 00:01:28,600 Și rama imediat de mai jos care are nevoie să aștepte 30 00:01:28,600 --> 00:01:33,560 până când este din nou cadru activ înainte de a putea relua activitatea. 31 00:01:33,560 --> 00:01:35,870 Când o funcție este completă și e gata, 32 00:01:35,870 --> 00:01:37,720 rama este mi-a venit de pe stivă. 33 00:01:37,720 --> 00:01:38,950 Asta e terminologia. 34 00:01:38,950 --> 00:01:41,110 Și rama imediat sub ea, ca tocmai am spus, 35 00:01:41,110 --> 00:01:42,880 devine noul cadru activ. 36 00:01:42,880 --> 00:01:45,960 >> Și dacă o numește o altă funcție, se va întrerupe din nou la. 37 00:01:45,960 --> 00:01:49,290 Cadru stiva că nouă funcție va fi împins pe partea de sus a stivei. 38 00:01:49,290 --> 00:01:50,650 Se va face lucrarea. 39 00:01:50,650 --> 00:01:52,100 S-ar putea pop înapoi. 40 00:01:52,100 --> 00:01:55,630 Și altă funcție de mai jos se poate relua din nou. 41 00:01:55,630 --> 00:02:00,080 >> Așa că haideți să trec prin asta din nou, în căutarea la ideea de a funcției factorial 42 00:02:00,080 --> 00:02:03,070 că am definit în recursivitate video pentru a vedea 43 00:02:03,070 --> 00:02:07,770 exact cum magia din spatele acestei proces recursiv are loc. 44 00:02:07,770 --> 00:02:09,870 Deci, aceasta este intreaga noastra fișier, nu? 45 00:02:09,870 --> 00:02:14,000 Am definit doi functions-- principală și de fapt. 46 00:02:14,000 --> 00:02:15,980 Și, după cum ne-am putea aștepta, orice program C se va 47 00:02:15,980 --> 00:02:18,470 să înceapă de la prima linie de principal. 48 00:02:18,470 --> 00:02:21,660 >> Deci, vom crea un nou cadru de stivă pentru principal. 49 00:02:21,660 --> 00:02:23,320 Și o să înceapă de funcționare. 50 00:02:23,320 --> 00:02:25,270 Solicită Principalele printf. 51 00:02:25,270 --> 00:02:29,390 Și printf va imprima factorial din 5. 52 00:02:29,390 --> 00:02:31,440 Ei bine, nu știe ce factorial de 5 este, 53 00:02:31,440 --> 00:02:35,620 și așa mai departe acest apel este deja în funcție de un alt apel de funcție. 54 00:02:35,620 --> 00:02:37,270 Deci principal este de gând să pauză acolo. 55 00:02:37,270 --> 00:02:39,103 Voi lăsa sa săgeată acolo, de culoare 56 00:02:39,103 --> 00:02:41,360 este aceeasi culoare ca și stivă cadru pe dreapta, 57 00:02:41,360 --> 00:02:47,720 pentru a indica faptul că principala este de gând să înghețe aici în timp ce factorial de 5 se numește. 58 00:02:47,720 --> 00:02:49,300 >> Deci, factorial de 5 se numește. 59 00:02:49,300 --> 00:02:53,160 Și se va incepe de la foarte începutul funcției factorial. 60 00:02:53,160 --> 00:02:55,440 Acesta solicită întrebarea sunt eu egal cu 1? 61 00:02:55,440 --> 00:02:56,810 Este de 5 egală cu 1? 62 00:02:56,810 --> 00:02:57,410 Ei bine, nu. 63 00:02:57,410 --> 00:03:01,110 Așa că va merge în jos pentru a else parte, întoarcerea de n ori 64 00:03:01,110 --> 00:03:02,990 factorial de n minus 1. 65 00:03:02,990 --> 00:03:03,490 Bine. 66 00:03:03,490 --> 00:03:07,070 >> Deci, acum, factorial de 5 este în funcție de un alt apel 67 00:03:07,070 --> 00:03:09,740 la factorial trece în 4 ca parametru. 68 00:03:09,740 --> 00:03:14,210 Și astfel factorialul 5 cadru, acel cadru roșu, 69 00:03:14,210 --> 00:03:17,160 este de gând să înghețe acolo la acea linie am arătat 70 00:03:17,160 --> 00:03:21,914 și așteptați pentru factorial de 4 pentru a termina ceea ce trebuie să facă, astfel încât, atunci 71 00:03:21,914 --> 00:03:23,330 poate deveni din nou cadru activ. 72 00:03:23,330 --> 00:03:26,890 >> Deci factorială a 4 începe la începutul factorial. 73 00:03:26,890 --> 00:03:28,556 Este de 4 egal cu 1? 74 00:03:28,556 --> 00:03:30,180 Nu, așa că va face același lucru. 75 00:03:30,180 --> 00:03:31,590 Se va merge în jos ramura altceva. 76 00:03:31,590 --> 00:03:33,240 Se va ajunge la acea linie de cod. 77 00:03:33,240 --> 00:03:35,710 OK, am de gând să se întoarcă de patru ori. 78 00:03:35,710 --> 00:03:41,270 Oh, factorial de 3-- astfel factoriale a 4 depinde factorial de 3 finisare. 79 00:03:41,270 --> 00:03:43,055 >> Și așa trebuie să solicite factorial de 3. 80 00:03:43,055 --> 00:03:45,180 Și asta o să treacă prin același proces din nou. 81 00:03:45,180 --> 00:03:48,200 Acesta începe prin, ajunge aici. 82 00:03:48,200 --> 00:03:50,980 Factorial de 3 depinde pe factorial de 1. 83 00:03:50,980 --> 00:03:53,750 Deci, factorial de 2 începe, ajunge aici. 84 00:03:53,750 --> 00:03:56,310 Depinde de factoriale de 1. 85 00:03:56,310 --> 00:03:57,430 Factorial de 1 începe. 86 00:03:57,430 --> 00:03:57,650 >> BINE. 87 00:03:57,650 --> 00:03:59,775 Deci, acum, ne apropiem undeva interesant, nu? 88 00:03:59,775 --> 00:04:02,190 Deci, acum, 1 este egal cu 1. 89 00:04:02,190 --> 00:04:05,130 Și astfel ne întoarcem 1. 90 00:04:05,130 --> 00:04:06,770 În acest moment, ne întoarcem. 91 00:04:06,770 --> 00:04:07,880 Funcția a făcut. 92 00:04:07,880 --> 00:04:11,140 Este un comportament este-- e nimic altceva pentru el să facă, 93 00:04:11,140 --> 00:04:17,006 și astfel încât cadrul stivei de factorial de 1 sare de pe. 94 00:04:17,006 --> 00:04:17,589 Este terminat. 95 00:04:17,589 --> 00:04:19,480 A revenit 1. 96 00:04:19,480 --> 00:04:23,370 Și acum, factorial de 2, care a fost cadrul imediat sub ea 97 00:04:23,370 --> 00:04:26,160 în stivă, devine cadru activ. 98 00:04:26,160 --> 00:04:29,030 >> Și se poate ridica exact unde a rămas. 99 00:04:29,030 --> 00:04:32,240 A fost de așteptare pentru un factorial din 1 pentru a termina lucrările sale. 100 00:04:32,240 --> 00:04:33,610 Ea a terminat acum. 101 00:04:33,610 --> 00:04:35,510 Și astfel, aici suntem. 102 00:04:35,510 --> 00:04:38,080 >> Factorial de 1 returnat o valoare de 1. 103 00:04:38,080 --> 00:04:42,430 Deci, factorial de 2 poate să zicem reveni de 2 ori 1. 104 00:04:42,430 --> 00:04:43,680 Activitatea sa este acum gata. 105 00:04:43,680 --> 00:04:49,110 Este revenit 2 la factoriale 3, care a fost de așteptare pentru ea. 106 00:04:49,110 --> 00:04:53,370 Factorial de 3 este acum rama superioară, cadrul activ în stivă. 107 00:04:53,370 --> 00:04:58,617 Și astfel se spune, OK, bine, am de gând să se întoarcă de 3 ori 2, care este 6. 108 00:04:58,617 --> 00:05:00,700 Și am de gând să dau asta valoare înapoi la factorial 109 00:05:00,700 --> 00:05:03,430 de 4, care a fost de așteptare pentru mine. 110 00:05:03,430 --> 00:05:04,500 Am terminat. 111 00:05:04,500 --> 00:05:09,410 Factorial de 3 apare pe stivă, și factorial de 4 este acum cadru activ. 112 00:05:09,410 --> 00:05:13,510 >> 4 spune, OK, am de gând să se întoarcă de 4 ori factorialul 3, care a fost de șase. 113 00:05:13,510 --> 00:05:15,980 Asta a fost de valoare care factorial de 3 a revenit. 114 00:05:15,980 --> 00:05:19,010 Și așa mai departe de 4 ori 6 este de 24. 115 00:05:19,010 --> 00:05:20,990 Și am de gând să treacă înapoi la factoriale 116 00:05:20,990 --> 00:05:23,160 de 5, care a fost de așteptare pentru mine. 117 00:05:23,160 --> 00:05:25,270 Factorial de 5 este acum cadrul activ. 118 00:05:25,270 --> 00:05:30,700 O să se întoarcă de 5 ori factorial de 4-- 5 ori 24, sau 120-- 119 00:05:30,700 --> 00:05:32,722 și să dea acea valoare Înapoi la care are 120 00:05:32,722 --> 00:05:35,680 fost de așteptare foarte răbdător pentru o lungă perioadă de timp în partea de jos a stivei. 121 00:05:35,680 --> 00:05:36,640 >> E în cazul în care a început. 122 00:05:36,640 --> 00:05:37,670 Ea a făcut acest apel. 123 00:05:37,670 --> 00:05:39,400 Mai multe cadre preluat în partea de sus. 124 00:05:39,400 --> 00:05:41,890 Acum este din nou pe partea de sus a stivei. 125 00:05:41,890 --> 00:05:43,450 Este cadru activ. 126 00:05:43,450 --> 00:05:47,810 Deci principal a primit valoarea de 120 înapoi la factorial de 5. 127 00:05:47,810 --> 00:05:50,750 A fost de așteptare pentru a imprima această valoare. 128 00:05:50,750 --> 00:05:51,657 Și apoi se face. 129 00:05:51,657 --> 00:05:53,240 Nu există E mai multe linii de cod în principal. 130 00:05:53,240 --> 00:05:56,800 Deci, cadrul principal de apare pe stiva, și am terminat. 131 00:05:56,800 --> 00:05:58,992 >> Și asta e modul în care funcționează recursivitate. 132 00:05:58,992 --> 00:06:00,200 Asta e modul în care funcționează cadre stiva. 133 00:06:00,200 --> 00:06:03,120 Aceste apeluri de funcții ce sa întâmplat anterior 134 00:06:03,120 --> 00:06:06,620 sunt doar pe pauză, așteptând pentru apelurile ulterioare 135 00:06:06,620 --> 00:06:12,050 pentru a termina astfel încât să poată deveni activ cadru și să termin ceea ce au nevoie să facă. 136 00:06:12,050 --> 00:06:13,060 >> Sunt Doug Lloyd. 137 00:06:13,060 --> 00:06:14,880 Acest lucru este CS50. 138 00:06:14,880 --> 00:06:16,580