דאג LLOYD: אם ראית הווידאו ברקורסיה, אולי יש לי כל התהליך נראה קצת קסום. איך זה עובד? איך הפונקציות יודעים שהם צריך לחכות ולחכות לערך אחר לחזור מתפקיד שונה קורא כדי לקבל את התוצאה שאנחנו רוצים? ובכן, הסיבה שזה עובד היא כי של משהו שנקרא שיחת מחסנית. כשאתה מתקשר לפונקציה, מערכת קובעת בצד חלל בזיכרון לפונקציה שכדי לעשות את העבודה שלה. ואנחנו קוראים נתחי זיכרון אלה ש מתבצע להפריש עבור כל פונקציה קורא מסגרת מחסנית או מסגרת תפקיד. וכפי שאפשר לצפות, מסגרות אלה הערימה חי על חלק הערימה של זיכרון. 

מסגרת ערימה יותר מאשר פונקציה אחת יכול להתקיים בזיכרון בזמן נתון. אם ראשי קורא מהלך פונקציה, ומהלך קורא כיוון, כל שלוש הפונקציות מסגרות פתוחות. אבל לא כל יש להם מסגרות פעילה. מסגרות אלה מסודרים בערימה. והמסגרת מ נקרא לאחרונה הפונקציה תמיד על ראש הערימה. וזה תמיד את המסגרת הפעילה. יש רק אחד באמת אי פעם פונקציה זו פעילה בכל זמן. זה אחד על ראש הערימה. 

כאשר פונקציה קוראת אחרת פונקציה, זה סוג של לוחצת הפסקה. זה סוג של בהמתנה, מחכה. ומסגרת ערימה אחרת נדחפה על הערימה על גבי זה. וזה הופך את המסגרת הפעילה. ואת המסגרת באופן מיידי מתחתיו צריך לחכות עד שהוא שוב המסגרת הפעילה לפני שניתן לחדש את העבודה שלה. כאשר פונקציה היא שלם וזה נעשה, המסגרת שלו צצה מהערימה. זה המינוח. ואת המסגרת באופן מיידי מתחתיו, כמו שאמרתי, הופך את המסגרת הפעילה החדשה. 

ואם הוא קורא פונקציה אחרת, זה הולך להשהות שוב. מסגרת המחסנית זה פונקציה החדשה תהיה להידחף אל ראש הערימה. זה יעשה את העבודה שלה. זה יכול לקפוץ אחורה מ. והפונקציה אחרת מתחתיו יכול לחדש שוב. 

אז בואו לעבור את זה שוב, מחפש ברעיון של פונקצית העצרת שהוגדרנו ב וידאו רקורסיה לראות בדיוק איך הקסם מאחורי זה תהליך רקורסיבית מתרחש. אז זה כל הקובץ שלנו, נכון? הגדרנו שני functions-- עיקרי ולמעשה. וכפי שהיינו מצפה, כל תכנית C הולכת כדי להתחיל בשורה הראשונה של עיקרי. 

אז אנחנו יוצרים מסגרת חדשה לערימה העיקרית. וזה הולך להתחיל ריצה. שיחות ראשי printf. וprintf הולך להדפיס את העצרת של 5. ובכן, זה לא יודע מה עצרת של 5 הוא, וכך שיחה זו היא כבר בהתאם לקריאה לפונקציה אחרת. אז עיקרי הולך להשהות ממש שם. אני הולך לעזוב אותה חץ שם, צבע זה באותו הצבע כמו מחסנית מסגרת בצד הימין, כדי לציין שעיקרי הולך להקפיא כאן בזמן עצרת של 5 נקראת. 

אז עצרת של 5 נקראת. וזה הולך להתחיל במאוד החל מפונקצית העצרת. זה שואל את השאלה אני שווה ל 1? האם 5 שווים ל 1? ובכן לא. אז זה הולך לרדת ל חלק, התמורה אחרת n פעמים עצרת של n מינוס 1. טוב, בסדר. 

אז עכשיו, עצרת של 5 היא בהתאם לשיחה אחרת לעצרת, שעבר ב 4 כפרמטר. וכך את העצרת של 5 מסגרת, שמסגרת אדומה, הולך להקפיא שם בקו שאני כבר הצביע ולחכות לעצרת של 4 כדי לסיים מה שהוא צריך לעשות כדי שאז זה יכול להיות המסגרת הפעילה שוב. 

אז עצרת של 4 מתחילה ב תחילת העצרת. האם 4 שווים ל 1? לא, כך שזה הולך לעשות את אותו הדבר. זה הולך לרדת סניף אחר. זה הולך להגיע לקו זה של קוד. אישור, אני הולך לחזור ארבע פעמים. אה, עצרת של 3-- כך עצרת של 4 תלויים בעצרת של 3 גמר. 

וכך זה צריך לקרוא עצרת של 3. וזה הולך לעבור את אותו התהליך שוב. זה מתחיל ב, מקבל כאן. עצרת של 3 תלויה בעצרת של 1. אז עצרת של 2 מתחיל, מקבל כאן. זה תלוי בעצרת של 1. עצרת של 1 מתחילה. 

אוקיי. אז עכשיו, אנחנו מקבלים מעניין איפשהו, נכון? אז עכשיו, 1 שווה ל -1. וכך אנו חוזרים 1. בשלב זה, אנחנו חוזרים. הפונקציה עושה את זה. זה התנהגות הוא-- יש שום דבר אחר עבורו לעשות, וכך מסגרת המחסנית ל העצרת של 1 קופצת מעל. זה גמור. זה חזר 1. ועכשיו, עצרת של 2, ש הייתה המסגרת מייד מתחתיו בערימה, הופך את המסגרת הפעילה. 

וזה יכול להרים בדיוק איפה שהוא נפסק. זה כבר מחכה לעצרת של 1 לסיים את עבודתה. זה עתה סיים. וכך אנחנו כאן. 

עצרת של 1 חזר ערך 1. אז עצרת של 2 פחית למשל לחזור 2 פעמים 1. עבודתה נעשתה עכשיו. זה חזר 2 לעצרת של 3, שמחכה לזה. עצרת של 3 היא החברה המסגרת העליונה, המסגרת הפעילה בערימה. ואז זה אומר, בסדר, טוב, אני הולך לחזור 3 פעמים 2, אשר היא 6. ואני הולך לתת לי ש מעריך בחזרה לעצרת של 4, שכבר מחכים לי. אני סיימתי. העצרת של 3 קופצת מעל הערימה, ו עצרת של 4 היא החברה המסגרת הפעילה. 

4 אומר, בסדר, אני הולך לחזור 4 פעמים העצרת של 3, שהיו שישה. זה היה ערך ש העצרת של 3 חזר. וכך 4 פעמים 6 היא 24. ואני הולך לעבור בחזרה לעצרת ש 5, אשר כבר מחכה לי. עצרת של 5 היא עכשיו המסגרת הפעילה. זה הולך לחזור 5 פעמים עצרת של 4-- 5 פעמים 24, או 120-- ולתת ערך ש בחזרה לעיקרי, שבו יש חיכה בסבלנות רבה ל זמן רב בתחתית הערימה. 

זה המקום שבו התחיל. זה עשה את השיחה הזו. מספר פריימים השתלטו בחלק העליון. עכשיו זה חזר על ראש הערימה. זה המסגרת הפעילה. אז ראשי קיבל את הערך 120 חזרה מעצרת של 5. זה כבר מחכה ל להדפיס את הערך ש. ואז עושה את זה. אין יותר שורות קוד בעיקרי. אז המסגרת של עיקרי קופצת מעל המחסנית, ואנחנו נעשו. 

וכך רקורסיה עובדת. ככה מסגרות ערימה לעבוד. אלה שיחות פונקציה זה קרה בעבר רק בהפסקה, מחכה עבור השיחות שלאחר מכן כדי לסיים כל כך שהם יכולים להיות פעילים למסגר ולסיים את מה שהם צריכים לעשות. 

אני דאג לויד. זה CS50.