ДАГ 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.