Даг Lloyd: Калі вы бачылі відэа на рэкурсіі,
увесь працэс можа мець Здавалася трохі чароўным.
Як гэта працуе?
Як функцыянуе ведаюць, што яны трэба чакаць і чакаць іншага значэння
вярнуцца з іншай функцыі тэлефануйце, каб атрымаць вынік, які мы хочам?
>> Ну, прычына гэтага ў тым, што працуе што-то вядомы як стэк выклікаў.
Калі вы выклікаеце функцыю, то Сістэма вылучае прастору ў памяці
для гэтай функцыі, каб зрабіць сваю працу.
І мы называем гэтыя кавалкі памяці, ствараюцца ў бок для кожнай функцыі
выклікаць стэка або функцыю кадра.
І, як вы маглі б чакаць, гэтыя кадры стэка
жыць на стэку часткі памяці.
>> Больш чым адну функцыю фрэйм ​​стэка можа існаваць у памяці ў дадзены момант часу.
Калі асноўны выклікае функцыю крок, і крок выклікае кірунак,
усе тры функцыі маюць адкрытыя рамкі.
Але не ўсе яны маюць актыўныя кадры.
Гэтыя кадры размешчаны ў стэку.
І кадр з нядаўна назваў
Функцыя заўсёды на вяршыні стэка.
І гэта заўсёды актыўны кадр.
Там толькі сапраўды калі-небудзь адным функцыя, актыўны адначасова.
Гэта адзін на вяршыні стэка.
>> Калі функцыя выклікае іншую Функцыя, ён накшталт націскае паўзу.
Гэта свайго роду знаходзіцца на ўтрыманні, чакаючы.
І яшчэ фрэйм ​​стэка выштурхваецца стэк-над ім.
І, што становіцца актыўным кадра.
І кадр адразу Ніжэй ён павінен чакаць
да таго часу, пакуль зноў актыўны кадр перш чым ён можа аднавіць сваю працу.
Калі функцыя поўнае і гэта будзе зроблена,
яго кадр з стэка.
Гэта тэрміналогія.
І кадр адразу пад ім, як я толькі што сказаў
становіцца новым актыўны кадр.
>> А калі яна выклікае іншую функцыю, ён збіраецца прыпыніць зноў.
Фрэйм стэка, што новыя функцыі будзе быць змяшчаецца ў вяршыні стэка.
Гэта будзе рабіць сваю працу.
Гэта можа поп адступіць.
І іншыя функцыі Ніжэй можна аднавіць зноў.
>> Такім чынам, давайце прайсці праз гэта зноў, гледзячы на ідэі функцыі фактарыяла
што мы вызначаны ў Рэкурсія відэа, каб убачыць
дакладна, як магія за гэтым рэкурсіўны працэс адбываецца.
Так што гэта ўсё наш файл, праўда?
Мы вызначылі два functions-- асноўны і факт.
І, як мы маглі б чакаць, любая праграма З адбываецца
каб пачаць на першай лініі галоўнай.
>> Так мы ствараем новы кадр стэка для асноўнай.
І гэта адбываецца, каб пачаць бег.
Асноўныя выклікі PRINTF.
І Printf збіраецца раздрукаваць фактарыяла 5.
Ну, ён не ведае, тое, што фактарыяла 5 з'яўляецца,
і так гэты выклік ўжо у залежнасці ад іншага выкліку функцыі.
Так галоўны збіраецца прыпыніць прама там.
Я збіраюся пакінуць яго стрэлка направа там, колер
гэта той жа колер, як стэк рамкі справа,
каб паказаць, што галоўная збіраецца замарозіць тут, а Фактарыял 5 называецца.
>> Так Фактарыял 5 называецца.
І гэта адбываецца, каб пачаць па меншай пачынаючы ад функцыі фактарыяла.
Гэта задае пытанне я роўная 1?
Ёсць 5 роўна 1?
Ну, няма.
Такім чынам, гэта будзе ісці ўніз, каб часткі інакш, вяртанне ў п раз
Фактарыяла N мінус 1.
Ну, добра.
>> Так што цяпер, Фактарыял 5 з'яўляецца у залежнасці ад іншай выклік
каб фактарыяла, праходзячы у 4 ў якасці параметру.
І так фактарыяла 5 кадраў, што чырвонай рамкай,
збіраецца замарозіць тут на гэтай лініі я ўказаў
і чакаць фактарыяла ад 4 да завяршэння тое, што трэба зрабіць так, каб потым яго
можа стаць актыўную рамку зноў.
>> Так Фактарыял 4 пачынаецца ў пачатак фактарыяла.
Ёсць 4 роўны 1?
Не, так ён збіраецца зрабіць тое ж самае.
Гэта збіраецца спусціцца яшчэ галіна.
Гэта адбываецца, каб дабрацца да гэтага радка кода.
ОК, я збіраюся вярнуцца ў чатыры разы.
О, Фактарыял 3-- так Фактарыял 4 залежыць ад фактарыяла 3 аздаблення.
>> І таму ён павінен патэлефанаваць фактарыяла 3.
І, што збіраецца прайсці той жа самы працэс зноў.
Яна пачынаецца праз, атрымлівае тут.
Фактарыяла 3 залежыць на фактарыяла 1.
Так Фактарыял 2 стартаў, атрымлівае тут.
Гэта залежыць ад фактарыяла 1.
Фактарыяла 1 стартаў.
>> ДОБРА.
Так што цяпер, мы атрымліваем дзе цікава, праўда?
Такім чынам, 1 роўны 1.
І так мы вяртаемся 1.
На дадзены момант, мы вяртаемся.
Функцыя зроблена.
Гэта паводзіны is-- ёсць нічога яшчэ для гэтага рабіць,
і таму кадр стэка для Фактарыяла 1 з'яўляецца ад.
Гэта скончана.
1 вяртаецца.
А цяпер, Фактарыял 2, што быў кадра непасрэдна пад ім
у стэку, становіцца актыўным кадра.
>> І гэта можа падабраць дзе менавіта спыніліся.
Гэта чакалі фактарыяла 1, каб скончыць сваю працу.
У цяперашні час скончана.
І вось мы тут.
>> Фактарыяла 1 вяртаецца значэнне 1.
Так Фактарыял 2 можа скажам вярнуць 2 разы 1.
Яго праца робіцца цяпер.
Гэта вярнуўся ад 2 да фактарыяла 3, які быў для яго чакаюць.
Фактарыяла 3 зараз верхняя рама, актыўны кадр у стэку.
І так ён кажа, добра, добра, я збіраюся вярнуцца 3 разы 2, які 6.
І я збіраюся даць, што значэнне назад фактарыяла
4, які чакаў мяне.
Я скончыў.
Фактарыяла 3 з'яўляецца з стэка, і Фактарыяла 4 зараз актыўны кадр.
>> 4 кажа, добра, я збіраюся вярнуцца ў 4 разы фактарыяла 3, што было шэсць гадоў.
Гэта было каштоўнае, што Фактарыяла 3 вяртаецца.
І так 4 разы чэрвені 24.
І я збіраюся прайсці што вярнуцца да фактарыяла
5, якая чакала мяне.
Фактарыяла 5 у цяперашні час актыўны кадр.
Гэта збіраецца вярнуцца ў 5 разоў Фактарыяла 4-- 5 разоў 24 або 120--
і даць, што значэнне на галоўную, якая мае
чакалі вельмі цярпліва для доўгі час у ніжняй частцы чаркі.
>> Гэта месца, дзе яна пачалася.
Ён зрабіў гэты выклік.
Некалькі кадраў ўзяў на сябе зверху.
Цяпер назад на вяршыні стэка.
Гэта актыўны кадр.
Так галоўны атрымалі значэнне 120 назад ад фактарыяла 5.
Гэта было чакаць, каб раздрукаваць гэтую велічыню.
А потым гэта робіцца.
Там няма больш радкоў кода ў асноўны.
Так каркас Галоўнае выскоквае ад стэк, і мы зрабілі.
>> І вось як працуе Рэкурсія.
Вось як кадры стэка працаваць.
Гэтыя выклікі функцый што адбылося раней
проста на паўзу, чакаючы для наступных выклікаў
да канца, каб яны маглі стаць актыўным кадр і скончыць тое, што яны павінны рабіць.
>> Я Дуг Лойд.
Гэта CS50.