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
זה יכול לקפוץ אחורה מ.

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
וכפי שהיינו מצפה,
כל תכנית C הולכת

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
זה התנהגות הוא-- יש
שום דבר אחר עבורו לעשות,

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