Дъг LLOYD: Ако сте виждали видеото на рекурсия, целият процес може да има Изглеждаше малко вълшебно. Как работи? Как функциите знаят, че те Трябва да изчакаме и да изчакаме още една стойност да се върне от различна функция обадя, за да се получи резултата, което искаме? Е, причината е, защото това работи на нещо, известно като стека повикване. Когато позвъните на функция, система заделя място в паметта за тази функция, за да си върши работата. И ние наричаме тези части от паметта, която се заделят за всяка функция обадете комин рамка или функция конструкция. И както може да се очаква, тези стека рамки живеят на стека част на паметта. 

Повече от една функция стека конструкция може да съществува в памет в даден момент. Ако основната призовава функция ход, и ход призовава посока, и трите функции са отворени рамки. Но те не всичко нужно активни рамки. Тези рамки са подредени в стека. И рамката от най-наскоро призова функция е винаги на върха на стека. И това е винаги активното рамката. Има само един наистина някога функция, която е активна в даден момент. Той е този, на върха на стека. 

Когато дадена функция призовава друг функция, тя някак преси пауза. Това нещо е задържана, чака. И още един стек конструкция е натиснат върху комина на върха му. И това става активна рамка. И рамката веднага под него трябва да се изчака докато е отново активното рамката преди да може да поднови работата си. Когато е функция пълна и това е направено, рамката му е извадена извън стека. Това е терминологията. И рамката веднага под него, както току-що каза, става новият активната рамка. 

И ако го нарича друга функция, то се случва да направите пауза отново. Стак конструкция Тази нова функция воля се вкарва на върха на купчината. Тя ще си върши работата. Тя може да се появи обратно на разстояние. И друга функция под него може да се възобнови отново. 

Така че нека да мине през това отново, гледайки до идеята за факторен функция че определени в рекурсия видео, за да видите точно как магията зад това рекурсивни процес се провежда. Така че това е цялата ни файл, нали? Ние определено две functions-- основна и факт. И както може да се очаква, всяко C програма ще да започва с първата линия на основната. 

Така че ние се създаде нов комин рамка за основното. И то се случва да се показват отново. Основни разговори ФОРМАТ. И ФОРМАТ ще разпечатате факториел от 5. Е, той не знае което факторен на 5, и така този разговор вече е в зависимост от друга функция повикване. Така че основното ще пауза точно там. Аз ще остави своя стрелка точно там, цветен тя със същия цвят като на стека конструкция отдясно, да се посочи, че основното ще замрази тук, докато факторен на 5 се нарича. 

Така факторен на 5 се нарича. И това ще започне в самото започваща на факторен функция. Той задава въпроса съм равен на 1? 5 е равно на 1? Ами не. Така, че ще ходи да слязат на друго участие, връщането н времена факторен на N минус 1. Е, OK. 

Така че сега, факториел от 5 е в зависимост от друг разговор да факторните, минаваща в 4 като параметър. И така на факториела 5 конструкция, която червена рамка, ще замрази точно там по тази линия съм посочено и да чакат за факторен на 4, за да продължи какво трябва да направи така, че след това го може да се превърне отново в активната рамка. 

Така факториела 4 започва в началото на факториален. 4 е равно на 1? Не, така че ще направи същото нещо. Това ще слязат на друг клон. Това ще стигнем до този ред код. OK, аз отивам да се върне четири пъти. О, факторен на 3-- така факториела 4 зависи от факторен на 3 довършителни работи. 

И така, той трябва да се обадя на факторен 3. И това ще мине през същия процес отново. Тя започва през, дойде тук. Факториел на 3 зависи на факториел на 1. Така факторен на 2 започва, получава тук. Това зависи от факторен на 1. Факториел на 1 започва. 

ДОБРЕ. Така че сега, ние получаваме някъде интересно, нали? Така че сега, едно е равно на 1. И така, ние се върне 1. В този момент, ние се връщаме. Функцията е направено. Това е поведение is-- има нищо друго, за да се направи, и така на стека рамката за факторен на 1 изскача. Свършено е. Той се върна 1. И сега, факторен на 2, което е рамката непосредствено под него в стека, става активна рамка. 

И това може да вдигне точно там, където е спряло. Той е бил в очакване на факториел 1, за да продължи работата си. Сега е приключил. И така, ние сме тук. 

Факториел на 1 завърна на стойност 1. Така факторен на 2 консерва да речем върне 2 пъти 1. Нейната работа е вече свършена. Той е върнал от 2 до факторните на 3, която го очакваше. Факториел на 3 сега е най-горната част на рамката, активното кадър в стека. И така се казва, OK, добре, аз ще съм да се върнат 3 пъти 2, което е 6. И аз ще дам, че ценим обратно към факторен 4, който е бил да ме чака. Приключих. Факториел на 3 изскача стека, и факторен на 4 сега е най-активната рамка. 

4 казва, OK, аз отивам да се върне 4 пъти факториела на 3, което е шест. Това беше на стойност, която факторен на 3 върнати. И така 4 пъти 6 е 24. И аз отивам да мине че обратно на факторните 5, който е бил да ме чака. Факториел на 5 вече е активна рамка. Това ще върне 5 пъти факторен на блок 4 5 пъти 24 или 120-- и да даде тази стойност обратно към основното, което има чакал търпеливо за дълго време в долната част на купчината. 

Това е мястото, където е започнало. Той направи този призив. Няколко кадъра превзеха в горната част. Сега е отново на върха на стека. Това е най-активната рамка. Така че основната получава стойност от 120 обратно от факториел от 5. Той е бил в очакване да разпечатате тази стойност. И тогава това е направено. Няма вече реда код в основната. Така че основната му конструкция изскача стека, и сме готови. 

И това е, как работи рекурсия. Ето как стека рамки работят. Тези извиквания , което се случи по-рано са само за пауза, очаквайки за следващи покани да завърши така, те могат да станат активната рамката и да завърши това, което трябва да направите. 

Аз съм Дъг Лойд. Това е CS50.