1 00:00:00,000 --> 00:00:05,587 2 00:00:05,587 --> 00:00:07,670 DOUG LLOYD: Hvis du har set videoen på rekursion, 3 00:00:07,670 --> 00:00:10,170 hele processen kan have syntes lidt magisk. 4 00:00:10,170 --> 00:00:10,930 Hvordan virker det? 5 00:00:10,930 --> 00:00:15,010 Hvordan funktionerne ved, at de nødt til at vente og vente på en anden værdi 6 00:00:15,010 --> 00:00:19,150 at vende tilbage fra en anden funktion ringe for at få det resultat, vi ønsker? 7 00:00:19,150 --> 00:00:22,550 >> Nå, grunden dette virker er, fordi af noget kendt som opkaldet stakken. 8 00:00:22,550 --> 00:00:26,360 Når du kalder en funktion, Systemet sætter til side plads i hukommelsen 9 00:00:26,360 --> 00:00:28,120 for denne funktion til at gøre sit arbejde. 10 00:00:28,120 --> 00:00:31,720 Og vi kalder disse bidder af hukommelse, er ved at blive afsat til hver funktion 11 00:00:31,720 --> 00:00:35,670 kalder en stak ramme eller en funktion ramme. 12 00:00:35,670 --> 00:00:38,290 Og som man kunne forvente, disse stakrammer 13 00:00:38,290 --> 00:00:41,000 bor på stakken del af hukommelsen. 14 00:00:41,000 --> 00:00:43,960 15 00:00:43,960 --> 00:00:47,540 >> Mere end én funktion stakrammen kan eksistere i hukommelsen på et givet tidspunkt. 16 00:00:47,540 --> 00:00:51,240 Hvis vigtigste kalder en funktion flytte, og flytte kalder retning, 17 00:00:51,240 --> 00:00:54,460 alle tre funktioner har åbne rammer. 18 00:00:54,460 --> 00:00:57,350 Men de har ikke alle har aktive rammer. 19 00:00:57,350 --> 00:00:59,410 Disse rammer er placeret i en stak. 20 00:00:59,410 --> 00:01:01,820 Og rammen fra senest kaldte 21 00:01:01,820 --> 00:01:04,390 Funktionen er altid på toppen af ​​stakken. 22 00:01:04,390 --> 00:01:07,150 Og det er altid den aktive ramme. 23 00:01:07,150 --> 00:01:10,420 Der er kun virkelig nogensinde én funktion, der er aktive ad gangen. 24 00:01:10,420 --> 00:01:12,420 Det er den ene oven på stakken. 25 00:01:12,420 --> 00:01:17,620 >> Når en funktion kalder en anden funktion, det slags presser pause. 26 00:01:17,620 --> 00:01:20,590 Den slags er i venteposition og venter. 27 00:01:20,590 --> 00:01:24,050 Og en anden stakramme skubbes på stakken på toppen af ​​det. 28 00:01:24,050 --> 00:01:26,150 Og der bliver den aktive ramme. 29 00:01:26,150 --> 00:01:28,600 Og rammen straks nedenfor er det nødvendigt at vente 30 00:01:28,600 --> 00:01:33,560 indtil det er igen den aktive ramme før det kan genoptage sit arbejde. 31 00:01:33,560 --> 00:01:35,870 Når en funktion er komplet og det er gjort, 32 00:01:35,870 --> 00:01:37,720 dets ramme springer fra stakken. 33 00:01:37,720 --> 00:01:38,950 Det er terminologien. 34 00:01:38,950 --> 00:01:41,110 Og rammen straks under det, som jeg lige har sagt, 35 00:01:41,110 --> 00:01:42,880 bliver det nye aktive ramme. 36 00:01:42,880 --> 00:01:45,960 >> Og hvis den kalder en anden funktion, det kommer til at holde pause igen. 37 00:01:45,960 --> 00:01:49,290 Denne nye funktion er stakrammen vil skubbes på toppen af ​​stakken. 38 00:01:49,290 --> 00:01:50,650 Det vil gøre sit arbejde. 39 00:01:50,650 --> 00:01:52,100 Det kunne pop tilbage fra. 40 00:01:52,100 --> 00:01:55,630 Og anden funktion under den kan genoptage igen. 41 00:01:55,630 --> 00:02:00,080 >> Så lad os gå igennem det igen, ser ved tanken om fakultet funktion 42 00:02:00,080 --> 00:02:03,070 at vi defineret i rekursion video for at se 43 00:02:03,070 --> 00:02:07,770 præcis, hvordan magien bag dette rekursive proces finder sted. 44 00:02:07,770 --> 00:02:09,870 Så det er hele vores fil, ikke? 45 00:02:09,870 --> 00:02:14,000 Vi definerede to functions-- vigtigste og kendsgerning. 46 00:02:14,000 --> 00:02:15,980 Og som vi kunne forvente, hvilken som helst C-programmet går 47 00:02:15,980 --> 00:02:18,470 at starte på den første linje af main. 48 00:02:18,470 --> 00:02:21,660 >> Så vi oprette en ny stakrammen til main. 49 00:02:21,660 --> 00:02:23,320 Og det kommer til at begynde at køre. 50 00:02:23,320 --> 00:02:25,270 Vigtigste opkald printf. 51 00:02:25,270 --> 00:02:29,390 Og printf vil udskrive fakultet af 5. 52 00:02:29,390 --> 00:02:31,440 Tja, det ikke kender hvad fakultet af 5 er, 53 00:02:31,440 --> 00:02:35,620 og så denne indkaldelse er allerede afhængig af en anden funktion opkald. 54 00:02:35,620 --> 00:02:37,270 Så vigtigste kommer til at holde pause lige der. 55 00:02:37,270 --> 00:02:39,103 Jeg vil forlade sin pil lige der, farve 56 00:02:39,103 --> 00:02:41,360 det samme farve som stak ramme til højre, 57 00:02:41,360 --> 00:02:47,720 at angive, at main kommer til at fryse her, mens fakultet af 5 hedder. 58 00:02:47,720 --> 00:02:49,300 >> Så fakultet af 5 hedder. 59 00:02:49,300 --> 00:02:53,160 Og det kommer til at starte på den meget begyndelsen af ​​fakulteten funktion. 60 00:02:53,160 --> 00:02:55,440 Det stiller spørgsmålet er jeg lig med 1? 61 00:02:55,440 --> 00:02:56,810 Er 5 lig med 1? 62 00:02:56,810 --> 00:02:57,410 Nå, nej. 63 00:02:57,410 --> 00:03:01,110 Så det kommer til at gå ned til else side afkast n gange 64 00:03:01,110 --> 00:03:02,990 fakultet af n minus 1. 65 00:03:02,990 --> 00:03:03,490 Nå, OK. 66 00:03:03,490 --> 00:03:07,070 >> Så nu, fakultet af 5 er afhængig af et andet opkald 67 00:03:07,070 --> 00:03:09,740 at faktoriel, der passerer i 4 som parameter. 68 00:03:09,740 --> 00:03:14,210 Og så fakultet af 5 stel, at rød ramme, 69 00:03:14,210 --> 00:03:17,160 kommer til at fryse dér på denne linje, jeg har angivet 70 00:03:17,160 --> 00:03:21,914 og vente på fakultet af 4 til slut hvad det skal gøre, så så er det 71 00:03:21,914 --> 00:03:23,330 kan blive den aktive ramme igen. 72 00:03:23,330 --> 00:03:26,890 >> Så fakultet af 4 starter på begyndelsen af ​​fakultet. 73 00:03:26,890 --> 00:03:28,556 Er 4 lig med 1? 74 00:03:28,556 --> 00:03:30,180 Nej, så det kommer til at gøre det samme. 75 00:03:30,180 --> 00:03:31,590 Det kommer til at gå ned i andet gren. 76 00:03:31,590 --> 00:03:33,240 Det kommer til at komme til denne linje kode. 77 00:03:33,240 --> 00:03:35,710 OK, jeg har tænkt mig at vende tilbage fire gange. 78 00:03:35,710 --> 00:03:41,270 Åh, fakultet af 3-- så fakultet af 4 afhænger fakultet af 3. efterbehandling. 79 00:03:41,270 --> 00:03:43,055 >> Og så er det nødvendigt at kalde fakultet af 3. 80 00:03:43,055 --> 00:03:45,180 Og det skal nok gå igennem den samme proces igen. 81 00:03:45,180 --> 00:03:48,200 Det begynder ved, kommer. 82 00:03:48,200 --> 00:03:50,980 Fakultet af 3 afhænger på fakultet af en. 83 00:03:50,980 --> 00:03:53,750 Så fakultet af 2 starter, får her. 84 00:03:53,750 --> 00:03:56,310 Det afhænger af fakultet af en. 85 00:03:56,310 --> 00:03:57,430 Fakultet af 1 starter. 86 00:03:57,430 --> 00:03:57,650 >> OK. 87 00:03:57,650 --> 00:03:59,775 Så nu er vi få et sted interessant, ikke? 88 00:03:59,775 --> 00:04:02,190 Så nu, 1 er lig med 1. 89 00:04:02,190 --> 00:04:05,130 Og så vender vi tilbage 1. 90 00:04:05,130 --> 00:04:06,770 På dette tidspunkt, er vi tilbage. 91 00:04:06,770 --> 00:04:07,880 Funktionen er gjort. 92 00:04:07,880 --> 00:04:11,140 Det er adfærd is-- der er ikke andet for at gøre, 93 00:04:11,140 --> 00:04:17,006 og så stakken ramme til fakultet af 1 springer ud. 94 00:04:17,006 --> 00:04:17,589 Den er færdig. 95 00:04:17,589 --> 00:04:19,480 Det returnerede 1. 96 00:04:19,480 --> 00:04:23,370 Og nu, fakultet af 2, som var rammen umiddelbart under det 97 00:04:23,370 --> 00:04:26,160 i stablen, bliver den aktive ramme. 98 00:04:26,160 --> 00:04:29,030 >> Og det kan afhente præcis hvor den slap. 99 00:04:29,030 --> 00:04:32,240 Det har været ventet på en faktorielt 1 for at afslutte sit arbejde. 100 00:04:32,240 --> 00:04:33,610 Dette er nu afsluttet. 101 00:04:33,610 --> 00:04:35,510 Og så her er vi. 102 00:04:35,510 --> 00:04:38,080 >> Fakultet af 1 returnerede en værdi på 1. 103 00:04:38,080 --> 00:04:42,430 Så fakultet af 2 dåse siger returnere 2 gange 1. 104 00:04:42,430 --> 00:04:43,680 Dets arbejde er nu udført. 105 00:04:43,680 --> 00:04:49,110 Det er returneret 2 til faktorielt af 3, der ventede på det. 106 00:04:49,110 --> 00:04:53,370 Fakultet af 3 er nu den øverste ramme, den aktive ramme i stablen. 107 00:04:53,370 --> 00:04:58,617 Og så det siger, OK, godt, jeg vil at vende tilbage 3 gange 2, hvilket er 6. 108 00:04:58,617 --> 00:05:00,700 Og jeg har tænkt mig at give denne værdsætter tilbage til fakultet 109 00:05:00,700 --> 00:05:03,430 4, er der ventet på mig. 110 00:05:03,430 --> 00:05:04,500 Jeg er færdig. 111 00:05:04,500 --> 00:05:09,410 Fakultet af 3 springer ud stakken, og fakultet af 4 er nu den aktive ramme. 112 00:05:09,410 --> 00:05:13,510 >> 4 siger, OK, jeg har tænkt mig at vende tilbage 4 gange fakultet af 3, hvilket var seks. 113 00:05:13,510 --> 00:05:15,980 Det var af værdi, fakultet af 3 tilbage. 114 00:05:15,980 --> 00:05:19,010 Og så 4 gange 6 er 24. 115 00:05:19,010 --> 00:05:20,990 Og jeg har tænkt mig at passere det tilbage til fakultet 116 00:05:20,990 --> 00:05:23,160 af 5, har som ventet på mig. 117 00:05:23,160 --> 00:05:25,270 Fakultet af 5 er nu den aktive ramme. 118 00:05:25,270 --> 00:05:30,700 Det kommer til at vende tilbage 5 gange fakultet af 4-- 5 gange 24 eller 120-- 119 00:05:30,700 --> 00:05:32,722 og give denne værdi tilbage til main, som har 120 00:05:32,722 --> 00:05:35,680 ventet meget tålmodigt for en lang tid ved bunden af ​​stakken. 121 00:05:35,680 --> 00:05:36,640 >> Det er hvor det startede. 122 00:05:36,640 --> 00:05:37,670 Det gjorde denne indkaldelse. 123 00:05:37,670 --> 00:05:39,400 Flere rammer overtog øverst. 124 00:05:39,400 --> 00:05:41,890 Det er nu tilbage på toppen af ​​stakken. 125 00:05:41,890 --> 00:05:43,450 Det er den aktive ramme. 126 00:05:43,450 --> 00:05:47,810 Så vigtigste fik værdien 120 tilbage fra fakultet af 5. 127 00:05:47,810 --> 00:05:50,750 Det er blevet venter på at udskrive denne værdi. 128 00:05:50,750 --> 00:05:51,657 Og så er det gjort. 129 00:05:51,657 --> 00:05:53,240 Der er ikke flere linjer kode i main. 130 00:05:53,240 --> 00:05:56,800 Så vigtigste ramme springer ud stakken, og vi er færdig. 131 00:05:56,800 --> 00:05:58,992 >> Og det er sådan rekursion fungerer. 132 00:05:58,992 --> 00:06:00,200 Det er, hvordan stakrammer virker. 133 00:06:00,200 --> 00:06:03,120 Disse funktionskald der skete tidligere 134 00:06:03,120 --> 00:06:06,620 er lige på pause, venter for de efterfølgende opkald 135 00:06:06,620 --> 00:06:12,050 til slut så de kan blive aktive indramme og afslutte, hvad de skal gøre. 136 00:06:12,050 --> 00:06:13,060 >> Jeg er Doug Lloyd. 137 00:06:13,060 --> 00:06:14,880 Det er CS50. 138 00:06:14,880 --> 00:06:16,580