1 00:00:00,000 --> 00:00:05,587 2 00:00:05,587 --> 00:00:07,670 Даг LLOYD: Ако сте виделе видео на рекурзија, 3 00:00:07,670 --> 00:00:10,170 целиот процес може да има се чинеше малку магично. 4 00:00:10,170 --> 00:00:10,930 Како работи? 5 00:00:10,930 --> 00:00:15,010 Како да функциите знаат дека тие треба да почекаме и да чека друга вредност 6 00:00:15,010 --> 00:00:19,150 да се врати од различна функција јавете се со цел да се добие резултат што сакаме? 7 00:00:19,150 --> 00:00:22,550 >> Добро, причината е поради тоа што се тоа функционира на нешто познато како магацинот на повикот. 8 00:00:22,550 --> 00:00:26,360 Кога ќе се јавите на функција, систем издвојува простор во меморијата 9 00:00:26,360 --> 00:00:28,120 за таа функција да ја врши својата работа. 10 00:00:28,120 --> 00:00:31,720 И ние го нарекуваме овие делови од меморијата која се резервирани за секоја функција 11 00:00:31,720 --> 00:00:35,670 јавете магацинот рамка или функција рамка. 12 00:00:35,670 --> 00:00:38,290 И како што би очекувале, овие магацинот рамки 13 00:00:38,290 --> 00:00:41,000 живеат на магацинот дел од меморијата. 14 00:00:41,000 --> 00:00:43,960 15 00:00:43,960 --> 00:00:47,540 >> Повеќе од една функција магацинот рамка може да постои во меморијата во дадено време. 16 00:00:47,540 --> 00:00:51,240 Ако главната повикува функција потег, и потег повикува насока, 17 00:00:51,240 --> 00:00:54,460 сите три функции има отворени рамки. 18 00:00:54,460 --> 00:00:57,350 Но, тие не се сите немаат активна рамки. 19 00:00:57,350 --> 00:00:59,410 Овие рамки се наредени во магацинот. 20 00:00:59,410 --> 00:01:01,820 И рамката од повикале 21 00:01:01,820 --> 00:01:04,390 функција е секогаш на врвот на магацинот. 22 00:01:04,390 --> 00:01:07,150 А тоа е секогаш активната рамка. 23 00:01:07,150 --> 00:01:10,420 Има само еден навистина некогаш функција која е активна во исто време. 24 00:01:10,420 --> 00:01:12,420 Тоа е еден на врвот на магацинот. 25 00:01:12,420 --> 00:01:17,620 >> Кога функциски повици на друг функција, тој вид на притиска пауза. 26 00:01:17,620 --> 00:01:20,590 Тоа на некој начин е на чекање, чекање. 27 00:01:20,590 --> 00:01:24,050 И уште магацинот рамка се турка врз оџакот на врвот на тоа. 28 00:01:24,050 --> 00:01:26,150 И тоа станува активна рамка. 29 00:01:26,150 --> 00:01:28,600 И рамката веднаш под него треба да се чека 30 00:01:28,600 --> 00:01:33,560 додека таа е повторно на активната рамка пред да може да продолжи со својата работа. 31 00:01:33,560 --> 00:01:35,870 Кога некоја функција е целосни и тоа е направено, 32 00:01:35,870 --> 00:01:37,720 рамката се појави надвор од магацинот. 33 00:01:37,720 --> 00:01:38,950 Тоа е терминологија. 34 00:01:38,950 --> 00:01:41,110 И рамката веднаш под неа, како што штотуку го кажав, 35 00:01:41,110 --> 00:01:42,880 станува новата активна рамка. 36 00:01:42,880 --> 00:01:45,960 >> И ако таа го нарекува друга функција, тоа се случува да се откажеш повторно. 37 00:01:45,960 --> 00:01:49,290 Магацинот рамка која нова функција волја да се турка кон врвот на магацинот. 38 00:01:49,290 --> 00:01:50,650 Тоа ќе го стори нејзината работа. 39 00:01:50,650 --> 00:01:52,100 Што би можеле да pop назад исклучување. 40 00:01:52,100 --> 00:01:55,630 А другата функција под него може да продолжи повторно. 41 00:01:55,630 --> 00:02:00,080 >> Па ајде да одиме преку ова, повторно, во потрага по идеја на факториел на 42 00:02:00,080 --> 00:02:03,070 дека ние се дефинирани во рекурзија видео за да видите 43 00:02:03,070 --> 00:02:07,770 точно како магија зад ова рекурзивен процес се случува. 44 00:02:07,770 --> 00:02:09,870 Значи ова е целата наша датотека, нели? 45 00:02:09,870 --> 00:02:14,000 Дефиниравме два functions-- главни и факт. 46 00:02:14,000 --> 00:02:15,980 И како што би очекувале, било Ц програма ќе 47 00:02:15,980 --> 00:02:18,470 за да започне во првата линија на главните. 48 00:02:18,470 --> 00:02:21,660 >> Значи ние се создаде нов магацинот рамка за главни. 49 00:02:21,660 --> 00:02:23,320 И тоа се случува да започне со трчање. 50 00:02:23,320 --> 00:02:25,270 Главната повици printf. 51 00:02:25,270 --> 00:02:29,390 Printf и ќе испечатите факториел од 5. 52 00:02:29,390 --> 00:02:31,440 Па, тоа не знае она факториел од 5 е, 53 00:02:31,440 --> 00:02:35,620 и така на овој повик е веќе во зависност од друг повик на функција. 54 00:02:35,620 --> 00:02:37,270 Значи главната ќе паузира право таму. 55 00:02:37,270 --> 00:02:39,103 Јас сум ќе ја напушти својата стрелка во право, таму, во боја 56 00:02:39,103 --> 00:02:41,360 тоа со иста боја како на магацинот рамка на десната страна, 57 00:02:41,360 --> 00:02:47,720 да се покаже дека главни се случува да се замрзне тука, додека факториел од 5 се нарекува. 58 00:02:47,720 --> 00:02:49,300 >> Па факториел од 5 се нарекува. 59 00:02:49,300 --> 00:02:53,160 И тоа се случува да се започне уште на самиот почнуваат на факториел на. 60 00:02:53,160 --> 00:02:55,440 Тоа го поставува прашањето сум еднаков на 1? 61 00:02:55,440 --> 00:02:56,810 Е 5 еднаков на 1? 62 00:02:56,810 --> 00:02:57,410 Добро, не. 63 00:02:57,410 --> 00:03:01,110 Па затоа се случува да одат надолу на друг дел, враќањето n пати 64 00:03:01,110 --> 00:03:02,990 факториел од n 1 минус. 65 00:03:02,990 --> 00:03:03,490 Па, ОК. 66 00:03:03,490 --> 00:03:07,070 >> Па сега, факториел од 5 е во зависност од друг повик 67 00:03:07,070 --> 00:03:09,740 да факториел, минувајќи во 4 како параметар. 68 00:03:09,740 --> 00:03:14,210 И така факториел од 5 рамка, која црвена рамка, 69 00:03:14,210 --> 00:03:17,160 се случува да се замрзне во право, таму во таа линија што сум наведено 70 00:03:17,160 --> 00:03:21,914 и да чекаат за факториел од 4 до крај она што треба да направите, така што потоа 71 00:03:21,914 --> 00:03:23,330 може да стане повторно активната рамка. 72 00:03:23,330 --> 00:03:26,890 >> Па факториел од 4 започнува во На почетокот на факториел. 73 00:03:26,890 --> 00:03:28,556 Е 4 еднаков на 1? 74 00:03:28,556 --> 00:03:30,180 Не, па затоа се случува да го направи истото. 75 00:03:30,180 --> 00:03:31,590 Тоа се случува да одат надолу по друго гранка. 76 00:03:31,590 --> 00:03:33,240 Тоа се случува да се дојде до таа линија код. 77 00:03:33,240 --> 00:03:35,710 Добро, јас ќе одам да се врати за четири пати. 78 00:03:35,710 --> 00:03:41,270 Ох, факториел од 3-- така факториел 4 зависи факториел од 3 финишира. 79 00:03:41,270 --> 00:03:43,055 >> И затоа таа треба да се јавите факториел од 3. 80 00:03:43,055 --> 00:03:45,180 А што е ќе помине низ истиот процес повторно. 81 00:03:45,180 --> 00:03:48,200 Таа започнува преку, добива тука. 82 00:03:48,200 --> 00:03:50,980 Факториел од 3 зависи на факториел од 1. 83 00:03:50,980 --> 00:03:53,750 Па факториел од 2 започнува, добива тука. 84 00:03:53,750 --> 00:03:56,310 Тоа зависи од факториел од 1. 85 00:03:56,310 --> 00:03:57,430 Факториел од 1 започнува. 86 00:03:57,430 --> 00:03:57,650 >> ВО РЕД. 87 00:03:57,650 --> 00:03:59,775 Па сега, ние сме добивање некаде интересно, нели? 88 00:03:59,775 --> 00:04:02,190 Па сега, 1 е еднаков на 1. 89 00:04:02,190 --> 00:04:05,130 И така се враќаме 1. 90 00:04:05,130 --> 00:04:06,770 Во овој момент, ние се враќаме. 91 00:04:06,770 --> 00:04:07,880 Функцијата е направено. 92 00:04:07,880 --> 00:04:11,140 Тоа е однесување is-- има ништо друго, за тоа да се направи, 93 00:04:11,140 --> 00:04:17,006 и така на магацинот рамка за факториел од 1 појавува надвор. 94 00:04:17,006 --> 00:04:17,589 Ќе заврши. 95 00:04:17,589 --> 00:04:19,480 Се врати 1. 96 00:04:19,480 --> 00:04:23,370 И сега, факториел од 2, кој беше рамката веднаш под него 97 00:04:23,370 --> 00:04:26,160 во магацинот, станува активен рамка. 98 00:04:26,160 --> 00:04:29,030 >> А тоа може да ги собереш токму онаму каде што застанавте. 99 00:04:29,030 --> 00:04:32,240 Тоа е се на чекање за факториел од 1 до крај својата работа. 100 00:04:32,240 --> 00:04:33,610 Сега тоа ќе заврши. 101 00:04:33,610 --> 00:04:35,510 И така тука сме. 102 00:04:35,510 --> 00:04:38,080 >> Факторијал од 1 врати вредност од 1. 103 00:04:38,080 --> 00:04:42,430 Па факториел од 2 може речеме вратат 2 пати 1. 104 00:04:42,430 --> 00:04:43,680 Неговата работа е сега направено. 105 00:04:43,680 --> 00:04:49,110 Се вратил од 2 до факториел на 3, кој е на чекање за него. 106 00:04:49,110 --> 00:04:53,370 Факториел од 3 сега е на врвот рамка, активната рамка во магацинот. 107 00:04:53,370 --> 00:04:58,617 И така се вели, Добро, добро, јас ќе одам за да се вратите 3 пати 2, што е 6. 108 00:04:58,617 --> 00:05:00,700 А јас ќе одам да се откаже од тоа вредност назад да факториел 109 00:05:00,700 --> 00:05:03,430 од 4, кој е на чекање за мене. 110 00:05:03,430 --> 00:05:04,500 Готов сум. 111 00:05:04,500 --> 00:05:09,410 Факториел од 3 појавува надвор од магацинот, и факториел од 4 сега е активната рамка. 112 00:05:09,410 --> 00:05:13,510 >> 4 вели: Добро, јас ќе одам да се вратат 4 пати факториел од 3, што е шест. 113 00:05:13,510 --> 00:05:15,980 Тоа беше од вредност кои факториел од 3 врати. 114 00:05:15,980 --> 00:05:19,010 И така 4 пати 6 е 24. 115 00:05:19,010 --> 00:05:20,990 А јас ќе одам да се помине дека назад во факториел 116 00:05:20,990 --> 00:05:23,160 од 5, кој е на чекање за мене. 117 00:05:23,160 --> 00:05:25,270 Факториел од 5 сега е активната рамка. 118 00:05:25,270 --> 00:05:30,700 Тоа се случува да се врати 5 пати факториел од 4-- 5 пати во 24, или 120-- 119 00:05:30,700 --> 00:05:32,722 и му даде на вредноста назад на главната, која има 120 00:05:32,722 --> 00:05:35,680 се чека многу трпеливо за долго време на дното на оџак. 121 00:05:35,680 --> 00:05:36,640 >> Тоа е каде што и започна. 122 00:05:36,640 --> 00:05:37,670 Тоа го направи на овој повик. 123 00:05:37,670 --> 00:05:39,400 Неколку рамки презеде на врвот. 124 00:05:39,400 --> 00:05:41,890 Тоа е сега се врати на врвот на магацинот. 125 00:05:41,890 --> 00:05:43,450 Тоа е активната рамка. 126 00:05:43,450 --> 00:05:47,810 Значи главната доби вредност 120 назад од факториел од 5. 127 00:05:47,810 --> 00:05:50,750 Тоа е се чека да се печатење на таа вредност. 128 00:05:50,750 --> 00:05:51,657 И тогаш тоа е направено. 129 00:05:51,657 --> 00:05:53,240 Нема повеќе линии на код во главниот. 130 00:05:53,240 --> 00:05:56,800 Така е главна рамка се појавува надвор магацинот, и сме подготвени. 131 00:05:56,800 --> 00:05:58,992 >> И тоа е тоа како работи рекурзијата. 132 00:05:58,992 --> 00:06:00,200 Тоа е како магацинот рамки работат. 133 00:06:00,200 --> 00:06:03,120 Оние функциски повици што се случи претходно 134 00:06:03,120 --> 00:06:06,620 се само на пауза, на чекање за следните повици 135 00:06:06,620 --> 00:06:12,050 за да се заврши, па тие може да стане активен обликувате и стави крај на она што тие треба да се направи. 136 00:06:12,050 --> 00:06:13,060 >> Јас сум Даг Лојд. 137 00:06:13,060 --> 00:06:14,880 Ова е CS50. 138 00:06:14,880 --> 00:06:16,580