1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: על מנת להבין
רקורסיה, עליך

3
00:00:10,190 --> 00:00:13,820
הראשונה מבין רקורסיה.

4
00:00:13,820 --> 00:00:17,280
לאחר רקורסיה באמצעי עיצוב תכנית
שיש לך קשרים עצמיים

5
00:00:17,280 --> 00:00:18,570
הגדרות.

6
00:00:18,570 --> 00:00:21,520
מבני נתונים רקורסיבית, למשל,
הם מבני נתונים ש

7
00:00:21,520 --> 00:00:23,990
כולל את עצמם ב
ההגדרות שלהם.

8
00:00:23,990 --> 00:00:27,160
אבל היום, אנחנו הולכים להתמקד
על פונקציות רקורסיבית.

9
00:00:27,160 --> 00:00:31,160
>> נזכיר כי פונקציות לקחת תשומות,
טיעונים, ולהחזיר ערך כמוהם

10
00:00:31,160 --> 00:00:34,480
פלט המיוצג על ידי
תרשים זה כאן.

11
00:00:34,480 --> 00:00:38,060
אנחנו נחשוב על התיבה כגוף של
הפונקציה, המכילה הסדרה של

12
00:00:38,060 --> 00:00:42,340
הוראות שמפרשות
קלט ולספק פלט.

13
00:00:42,340 --> 00:00:45,660
במבט מעמיק יותר בתוך הגוף של
הפונקציה יכולה לחשוף שיחות

14
00:00:45,660 --> 00:00:47,430
פונקציות אחרות גם כן.

15
00:00:47,430 --> 00:00:51,300
קח את התפקיד הזה פשוט, foo, כי
לוקח מחרוזת אחת כקלט ו

16
00:00:51,300 --> 00:00:54,630
הדפסים כמה אותיות
יש מחרוזת ש.

17
00:00:54,630 --> 00:00:58,490
Strlen הפונקציה, לאורך מחרוזת,
הוא נקרא, שתפוקתם היא

18
00:00:58,490 --> 00:01:01,890
הנדרש לקריאה לprintf.

19
00:01:01,890 --> 00:01:05,770
>> עכשיו, מה עושה פונקציה רקורסיבית
מיוחד הוא שזה קורא לעצמו.

20
00:01:05,770 --> 00:01:09,610
אנחנו יכולים לייצג רקורסיבית זה
להתקשר עם החץ הכתום הזה

21
00:01:09,610 --> 00:01:11,360
לולאה חזרה לעצמו.

22
00:01:11,360 --> 00:01:15,630
אבל ביצוע עצמו שוב רק יהיה
לעשות עוד שיחה רקורסיבית, ו

23
00:01:15,630 --> 00:01:17,150
עוד אחד ועוד.

24
00:01:17,150 --> 00:01:19,100
אבל פונקציות רקורסיבית
לא יכול להיות אינסופי.

25
00:01:19,100 --> 00:01:23,490
הם צריכים בסופו איכשהו, או שלך
תכנית תפעל לנצח.

26
00:01:23,490 --> 00:01:27,680
>> אז אנחנו צריכים למצוא דרך לשבור
מתוך השיחות רקורסיבית.

27
00:01:27,680 --> 00:01:29,900
אנחנו קוראים לזה במקרה הבסיס.

28
00:01:29,900 --> 00:01:33,570
כאשר מקרה בסיס התנאי מתקיים,
הפונקציה מחזירה מבלי לבצע

29
00:01:33,570 --> 00:01:34,950
אחר קריאה רקורסיבית.

30
00:01:34,950 --> 00:01:39,610
קח את התפקיד הזה, היי, פונקציה מבוטלת
שלוקח n int כקלט.

31
00:01:39,610 --> 00:01:41,260
מקרה הבסיס מגיע ראשון.

32
00:01:41,260 --> 00:01:46,220
אם n הוא פחות מאפס, ביי והדפסה
תמורה לכל המקרים האחרים,

33
00:01:46,220 --> 00:01:49,400
הפונקציה תדפיס היי ולבצע
הקריאה רקורסיבית.

34
00:01:49,400 --> 00:01:53,600
שיחה נוספת להיי הפונקציה עם
ערך קלט מופחת.

35
00:01:53,600 --> 00:01:56,790
>> עכשיו, למרות שאנחנו להדפיס היי,
פונקציה לא תסתיים עד ש

36
00:01:56,790 --> 00:02:00,370
לחזור סוג ההחזרה שלו,
במקרה החלל הזה.

37
00:02:00,370 --> 00:02:04,830
אז לכל n אחר מאשר מקרה הבסיס,
היי בפונקציה זו תחזיר ההיי

38
00:02:04,830 --> 00:02:06,890
של n מינוס 1.

39
00:02:06,890 --> 00:02:10,050
מאז פונקציה זו אם כי הוא בטל, אנחנו
לא באופן מפורש הקלד לחזור לכאן.

40
00:02:10,050 --> 00:02:12,000
אנחנו פשוט להפעיל את הפונקציה.

41
00:02:12,000 --> 00:02:16,960
אז קורא היי (3) יודפס היי ו
ביצוע היי (2), אשר מבצע היי (1) אחד

42
00:02:16,960 --> 00:02:20,560
אשר מבצע היי (0), שבו
מקרה בסיס תנאי מתקיים.

43
00:02:20,560 --> 00:02:24,100
אז היי (0) מדפיס שלום וחוזר.

44
00:02:24,100 --> 00:02:24,990
>> על אישור.

45
00:02:24,990 --> 00:02:28,690
אז עכשיו שאנחנו מבינים את היסודות של
פונקציות רקורסיבית, שהם צריכים

46
00:02:28,690 --> 00:02:32,730
מקרה בסיס אחד לפחות, כמו גם
קריאה רקורסיבית, בואו נעבור ל

47
00:02:32,730 --> 00:02:34,120
דוגמא משמעותית יותר.

48
00:02:34,120 --> 00:02:37,830
אחד שלא רק יחזור
ביטול לא משנה מה.

49
00:02:37,830 --> 00:02:41,340
>> בואו נסתכל על העצרת
פעולה הנפוצה ביותר ב

50
00:02:41,340 --> 00:02:43,660
חישובי הסתברות.

51
00:02:43,660 --> 00:02:48,120
עצרת של n היא התוצר של כל
מספר חיובי פחות מ

52
00:02:48,120 --> 00:02:49,400
ושווה ל-n.

53
00:02:49,400 --> 00:02:56,731
חמישה אז עצרת הוא 5 פעמים 4 פעמים
3 פעמים 2 פעמים 1 לתת 120.

54
00:02:56,731 --> 00:03:01,400
ארבע עצרת היא 4 פעמים 3 פעמים
2 פעמים 1 לתת 24.

55
00:03:01,400 --> 00:03:04,910
ואת אותו כלל חל
לכל מספר שלם חיובי.

56
00:03:04,910 --> 00:03:08,670
>> אז איך אנחנו יכולים לכתוב רקורסיבית
פונקציה שמחשבת את העצרת

57
00:03:08,670 --> 00:03:09,960
של מספר?

58
00:03:09,960 --> 00:03:14,700
ובכן, אנחנו נצטרך לזהות שתי
מקרה בסיס והקריאה רקורסיבית.

59
00:03:14,700 --> 00:03:18,250
הקריאה רקורסיבית לא תהיה אותו הדבר
בכל המקרים, פרט לבסיס

60
00:03:18,250 --> 00:03:21,420
מקרה, מה שאומר שנצטרך
למצוא דפוס שייתן לנו שלנו

61
00:03:21,420 --> 00:03:23,350
תוצאה רצויה.

62
00:03:23,350 --> 00:03:30,270
>> בדוגמה זו, לראות איך עצרת 5
כרוך הכפלת 4 ב -3 על ידי 2 ב -1

63
00:03:30,270 --> 00:03:33,010
וממש באותו כפל
נמצא כאן,

64
00:03:33,010 --> 00:03:35,430
הגדרה של 4 עצרת.

65
00:03:35,430 --> 00:03:39,810
כך אנו רואים כי 5 עצרת היא
רק 5 פעמים עצרת 4.

66
00:03:39,810 --> 00:03:43,360
עכשיו אין דפוס זה חלים
ל4 עצרת גם כן?

67
00:03:43,360 --> 00:03:44,280
כן.

68
00:03:44,280 --> 00:03:49,120
אנו רואים כי 4 עצרת מכילה את
כפל 3 פעמים 2 פעמים 1,

69
00:03:49,120 --> 00:03:51,590
מאוד הגדרה כ3 עצרת.

70
00:03:51,590 --> 00:03:56,950
אז 4 עצרת שווה ל 4 פעמים 3
עצרת, וכן הלאה וכן הלאה

71
00:03:56,950 --> 00:04:02,170
דפוס מקלות עד עצרת 1, אשר
מעצם הגדרתו הוא שווה ל 1.

72
00:04:02,170 --> 00:04:04,950
>> אין חיובי אחרים
מספרים שלמים עזבו.

73
00:04:04,950 --> 00:04:07,870
אז יש לנו את הדפוס עבור
הקריאה רקורסיבית שלנו.

74
00:04:07,870 --> 00:04:13,260
n העצרת שווה לפעמי n
העצרת של n מינוס 1.

75
00:04:13,260 --> 00:04:14,370
ומקרה הבסיס שלנו?

76
00:04:14,370 --> 00:04:17,370
שרק אהיה ההגדרה שלנו
של עצרת 1.

77
00:04:17,370 --> 00:04:19,995
>> אז עכשיו אנחנו יכולים לעבור לכתיבה
קוד לפונקציה.

78
00:04:19,995 --> 00:04:24,110
למקרה הבסיס, תהיה לנו
n המצב שווה שווה 1, שבו

79
00:04:24,110 --> 00:04:25,780
נחזור 1.

80
00:04:25,780 --> 00:04:29,280
לאחר מכן לנוע על הקריאה רקורסיבית,
נחזור פעמים n

81
00:04:29,280 --> 00:04:32,180
עצרת של n מינוס 1.

82
00:04:32,180 --> 00:04:33,590
>> עכשיו בואו לבודקנו זה.

83
00:04:33,590 --> 00:04:35,900
בואו ננסה עצרת 4.

84
00:04:35,900 --> 00:04:39,420
לפונקציה שלנו זה שווה
עד 4 פעמים עצרת (3).

85
00:04:39,420 --> 00:04:43,040
העצרת (3) שווה ל
3 פעמים עצרת (2).

86
00:04:43,040 --> 00:04:48,700
העצרת (2) שווה ל 2 פעמים
עצרת (1), שמחזיר 1.

87
00:04:48,700 --> 00:04:52,490
עצרת (2) החברה מחזירה 2 פעמים 1, 2.

88
00:04:52,490 --> 00:04:55,960
עצרת (3) יכולה עכשיו לחזור
3 פעמים 2, 6.

89
00:04:55,960 --> 00:05:02,490
ולבסוף, עצרת (4)
מחזיר 4 פעמים 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> אם אתה נתקלת בכל קושי
עם הקריאה רקורסיבית, להעמיד פנים ש

91
00:05:06,780 --> 00:05:09,660
הפונקציה עובדת כבר.

92
00:05:09,660 --> 00:05:13,450
מה שאני מתכוון זה שאתה צריך
סומך על השיחות רקורסיבית לחזור

93
00:05:13,450 --> 00:05:15,100
הערכים תקין.

94
00:05:15,100 --> 00:05:18,960
למשל, אם אני יודע ש
עצרת (5) שווה פי 5

95
00:05:18,960 --> 00:05:24,870
עצרת (4), אני הולך לתת אמון כי
עצרת (4) תיתן לי 24.

96
00:05:24,870 --> 00:05:28,510
תחשבו על זה כעל משתנה, אם אתה
יהיה, כאילו אתה כבר הוגדר

97
00:05:28,510 --> 00:05:30,070
עצרת (4).

98
00:05:30,070 --> 00:05:33,850
אז לכל עצרת (n), זה
המוצר של n ו

99
00:05:33,850 --> 00:05:35,360
העצרת הקודמת.

100
00:05:35,360 --> 00:05:38,130
ועצרת קודמת זה
מתקבל על ידי קורא

101
00:05:38,130 --> 00:05:41,330
עצרת של n מינוס 1.

102
00:05:41,330 --> 00:05:45,130
>> עכשיו, לראות אם אתה יכול ליישם
רקורסיבית לתפקד בעצמך.

103
00:05:45,130 --> 00:05:50,490
טען עד המסוף שלך, או run.cs50.net,
ולכתוב סכום פונקציה

104
00:05:50,490 --> 00:05:54,770
שלוקח n מספר שלם ומחזיר את
סכום של כל ברציפות החיובית

105
00:05:54,770 --> 00:05:57,490
מספרים שלמים מ n עד 1.

106
00:05:57,490 --> 00:06:01,000
שכתבתי את הסכומים של כמה
ערכים שיעזרו לך שלנו.

107
00:06:01,000 --> 00:06:04,030
ראשית, להבין את
מקרה בסיס מצב.

108
00:06:04,030 --> 00:06:06,170
ואז, מסתכל על הסכום (5).

109
00:06:06,170 --> 00:06:09,270
האם אתה יכול להביע את זה במונחים
מסכום אחר?

110
00:06:09,270 --> 00:06:11,290
עכשיו, מה עם סכום (4)?

111
00:06:11,290 --> 00:06:15,630
איך אתה יכול להביע את הסכום (4)
במונחים של סכום אחר?

112
00:06:15,630 --> 00:06:19,655
>> ברגע שיש לך סכום (5) וסכום (4)
באו לידי ביטוי במונחים של סכומים אחרים, ראה

113
00:06:19,655 --> 00:06:22,970
אם אתה יכול לזהות
דפוס לסכום (n).

114
00:06:22,970 --> 00:06:26,190
אם לא, נסה כמה מספרים אחרים
ולבטא אותם בסכומים

115
00:06:26,190 --> 00:06:28,410
מבחינת מספרים אחר.

116
00:06:28,410 --> 00:06:31,930
על ידי זיהוי דפוסים לבדידים
מספרים, אתה גם על הדרך שלך

117
00:06:31,930 --> 00:06:34,320
זיהוי הדפוס לכל n.

118
00:06:34,320 --> 00:06:38,040
>> רקורסיה היא כלי חזק באמת,
אז כמובן שזה לא מוגבל ל

119
00:06:38,040 --> 00:06:39,820
פונקציות מתמטיות.

120
00:06:39,820 --> 00:06:44,040
ניתן להשתמש ברקורסיה בצורה יעילה מאוד
כאשר מדוברים בעצים למשל.

121
00:06:44,040 --> 00:06:47,210
עזיבה הקצרה על עצים עבור
ביקורת מעמיקה יותר, אך לעת עתה

122
00:06:47,210 --> 00:06:51,140
זוכר שעצי החיפוש בינארי, ב
בפרט, בנויים מצומת, כל אחד

123
00:06:51,140 --> 00:06:53,820
עם ערך ושני מצביעי צומת.

124
00:06:53,820 --> 00:06:57,270
בדרך כלל, זה מיוצג על ידי
צומת הורה שיש הצבעה שורה אחת

125
00:06:57,270 --> 00:07:01,870
לצומת הילד השמאלית ואחד
לצומת הילד הנכונה.

126
00:07:01,870 --> 00:07:04,510
המבנה של חיפוש בינארי
עץ משאיל את עצמו היטב

127
00:07:04,510 --> 00:07:05,940
לחיפוש רקורסיבית.

128
00:07:05,940 --> 00:07:09,730
הקריאה רקורסיבית עוברת גם ב
שמאל או את הצומת הנכונה, אבל יותר

129
00:07:09,730 --> 00:07:10,950
מזה בטווח הקצר העץ.

130
00:07:10,950 --> 00:07:15,690
>> תגיד אתה רוצה לבצע פעולה על
כל צומת בעץ בינארי.

131
00:07:15,690 --> 00:07:17,410
איך שאתה יכול ללכת על זה?

132
00:07:17,410 --> 00:07:20,600
ובכן, אתה יכול לכתוב רקורסיבית
פונקציה שמבצעת את הפעולה

133
00:07:20,600 --> 00:07:24,450
בצומת ההורה וגורם רקורסיבית
להתקשר לאותו התפקיד,

134
00:07:24,450 --> 00:07:27,630
עובר בצד השמאל ו
בלוטות לילד נכון.

135
00:07:27,630 --> 00:07:31,650
לדוגמא, בפונקציה זו, foo, כי
משנה את הערך של צומת נתון ו

136
00:07:31,650 --> 00:07:33,830
כל הילדים שלה עד 1.

137
00:07:33,830 --> 00:07:37,400
מקרה הבסיס של גורמי צומת null
הפונקציה לחזור, המציין

138
00:07:37,400 --> 00:07:41,290
שאין כל צמתים
עזב שבתת עץ.

139
00:07:41,290 --> 00:07:42,620
>> בואו לעבור את זה.

140
00:07:42,620 --> 00:07:44,340
ההורה הראשון הוא 13.

141
00:07:44,340 --> 00:07:47,930
אנחנו משנים את הערך ל 1, ואז להתקשר
הפונקציה שלנו בצד השמאל, כמו גם

142
00:07:47,930 --> 00:07:49,600
כנכון.

143
00:07:49,600 --> 00:07:53,910
הפונקציה, foo, נקראת משמאל
תת עץ ראשון, ולכן את הצומת השמאלית

144
00:07:53,910 --> 00:07:57,730
יוקצה מחדש לfoo 1 ויהיה
להיקרא על הילדים של הצומת ש,

145
00:07:57,730 --> 00:08:01,900
ראשון משמאל ולאחר מכן ימינה,
וכן הלאה וכן הלאה.

146
00:08:01,900 --> 00:08:05,630
ולומר להם שאין להם סניפים
כל עוד ילדים כל כך את אותו התהליך

147
00:08:05,630 --> 00:08:09,700
ימשיך לילדים תקין
עד צמתים השלם של העץ הם

148
00:08:09,700 --> 00:08:11,430
מחדש ל1.

149
00:08:11,430 --> 00:08:15,390
>> כפי שאתה יכול לראות, אתה לא מוגבל
רק אחד קריאה רקורסיבית.

150
00:08:15,390 --> 00:08:17,930
בדיוק רבים ככל יקבל את העבודה.

151
00:08:17,930 --> 00:08:21,200
מה אם היה לך עץ שבו כל
הייתה לי צומת שלושה ילדים,

152
00:08:21,200 --> 00:08:23,100
שמאל, באמצע, ונכון?

153
00:08:23,100 --> 00:08:24,886
איך היית לערוך foo?

154
00:08:24,886 --> 00:08:25,860
ובכן, פשוט.

155
00:08:25,860 --> 00:08:30,250
רק להוסיף עוד קריאה רקורסיבית ו
תעבור במצביע צומת אמצע.

156
00:08:30,250 --> 00:08:34,549
>> רקורסיה היא חזקה מאוד ולא
להזכיר אלגנטי, אבל זה יכול להיות

157
00:08:34,549 --> 00:08:38,010
מושג קשה בהתחלה, כדי להיות
סבלני ולקחת את הזמן שלך.

158
00:08:38,010 --> 00:08:39,370
התחל עם מקרה הבסיס.

159
00:08:39,370 --> 00:08:42,650
זה בדרך כלל הקל לזהות,
ואז אתה יכול לעבוד

160
00:08:42,650 --> 00:08:43,830
לאחור משם.

161
00:08:43,830 --> 00:08:46,190
אתה יודע שאתה צריך להגיע אליך
מקרה בסיס, ולכן כוח ש

162
00:08:46,190 --> 00:08:47,760
אתן לך כמה רמזים.

163
00:08:47,760 --> 00:08:53,120
נסה לבטא מקרה אחד ספציפי ב
מבחינת מקרים אחרים, או בתת קבוצות.

164
00:08:53,120 --> 00:08:54,700
>> תודה על צפייה את זה קצר.

165
00:08:54,700 --> 00:08:58,920
לכל הפחות, עכשיו אתה יכול
מבין בדיחות כמו זה.

166
00:08:58,920 --> 00:09:01,250
השם שלי הוא Zamyla, וזה cs50.

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> קח את התפקיד הזה, היי,
פונקצית חלל שלוקחת

169
00:09:07,170 --> 00:09:09,212
int, n, כקלט.

170
00:09:09,212 --> 00:09:11,020
מקרה הבסיס מגיע ראשון.

171
00:09:11,020 --> 00:09:14,240
אם n הוא פחות מ 0, הדפסה
"שלום" ולחזור.

172
00:09:14,240 --> 00:09:15,490