1
00:00:00,000 --> 00:00:05,860
>> [השמעת מוסיקה]

2
00:00:05,860 --> 00:00:09,530
>> דאג LLOYD: אתה בטח חושב ש
קוד הוא רק משמש לביצוע מטלה.

3
00:00:09,530 --> 00:00:10,450
אתה כותב את זה.

4
00:00:10,450 --> 00:00:11,664
זה עושה משהו.

5
00:00:11,664 --> 00:00:12,580
זה פחות או יותר אותו.

6
00:00:12,580 --> 00:00:13,160
>> אתה לקמפל את זה.

7
00:00:13,160 --> 00:00:13,993
אתה מפעיל את התכנית.

8
00:00:13,993 --> 00:00:15,370
אתה טוב ללכת.

9
00:00:15,370 --> 00:00:17,520
>> אבל תאמינו או לא, אם
אתה קוד במשך זמן רב,

10
00:00:17,520 --> 00:00:20,550
אתה באמת יכול לבוא לראות
קוד כמו משהו שהוא יפה.

11
00:00:20,550 --> 00:00:23,275
זה פותר בעיה ב
דרך מאוד מעניינת,

12
00:00:23,275 --> 00:00:26,510
או שיש רק משהו באמת
מסודר על הדרך זה נראה.

13
00:00:26,510 --> 00:00:28,750
ייתכן שאתה צוחק
עליי, אבל זה נכון.

14
00:00:28,750 --> 00:00:31,530
ורקורסיה היא אחת דרכים
כדי לקבל את הרעיון הזה סוג של

15
00:00:31,530 --> 00:00:34,090
קוד של יפה, למראה אלגנטי.

16
00:00:34,090 --> 00:00:37,740
זה פותר בעיות בדרכים ש
מעניינים, קל לדמיין,

17
00:00:37,740 --> 00:00:39,810
וקצר באופן מפתיע.

18
00:00:39,810 --> 00:00:43,190
>> עבודות רקורסיה הדרך
היא, פונקציה רקורסיבית

19
00:00:43,190 --> 00:00:49,291
מוגדר כפונקציה שקוראת
עצמו כחלק מהביצוע שלה.

20
00:00:49,291 --> 00:00:51,790
זה אולי נראה קצת מוזר,
ואנו רואים קצת

21
00:00:51,790 --> 00:00:53,750
על איך זה עובד ברגע.

22
00:00:53,750 --> 00:00:55,560
אבל שוב, אלה
נהלים רקורסיבית הם

23
00:00:55,560 --> 00:00:57,730
הולך להיות כל כך אלגנטי
כי הם הולכים

24
00:00:57,730 --> 00:01:00,410
כדי לפתור בעיה זו ללא
יש את כל פונקציות אחרות אלה

25
00:01:00,410 --> 00:01:02,710
או הלולאות הארוכות הללו.

26
00:01:02,710 --> 00:01:06,310
אתה תראה שרקורסיבית אלה
נהלים הולכים להיראות כל כך קצר.

27
00:01:06,310 --> 00:01:10,610
והם באמת הולכים לעשות
הקוד שלך נראה הרבה יותר יפה.

28
00:01:10,610 --> 00:01:12,560
>> אני אתן לך דוגמא
זה כדי לראות איך

29
00:01:12,560 --> 00:01:14,880
הליך רקורסיבית יכול להיות מוגדר.

30
00:01:14,880 --> 00:01:18,202
אז אם אתה מכיר את זה
משיעור מתמטיקה לפני שנים רבות,

31
00:01:18,202 --> 00:01:20,910
יש משהו שנקרא
פונקצית עצרת, שהיא בדרך כלל

32
00:01:20,910 --> 00:01:25,340
מסומן כנקודה, סימן קריאה ש
מוגדר על כל המספרים השלמים וחיוביים.

33
00:01:25,340 --> 00:01:28,850
ואופן שבו n
העצרת מחושבת

34
00:01:28,850 --> 00:01:31,050
הוא להכפיל כל
המספרים פחות מ

35
00:01:31,050 --> 00:01:33,750
או שווה לtogether-- n
כל המספרים השלמים פחות מ

36
00:01:33,750 --> 00:01:34,880
או שווה ל n ביחד.

37
00:01:34,880 --> 00:01:39,850
>> אז 5 עצרת היא 5 פעמים
4 פעמים 3 פעמים 2 פעמים 1.

38
00:01:39,850 --> 00:01:43,020
ו -4 עצרת היא 4 פעמים
3 פעמים 2 פעמים 1 וכן הלאה.

39
00:01:43,020 --> 00:01:44,800
אתה מבין את הרעיון.

40
00:01:44,800 --> 00:01:47,060
>> כמתכנתים, אנחנו לא
להשתמש n, סימן קריאה.

41
00:01:47,060 --> 00:01:51,840
אז אנחנו מגדירים את העצרת
פונקציה כעובדה של n.

42
00:01:51,840 --> 00:01:56,897
ואנו נשתמש עצרת ליצור
פתרון רקורסיבית לבעיה.

43
00:01:56,897 --> 00:01:59,230
ואני חושב שאתה עלול למצוא
שזה הרבה יותר מבחינה ויזואלית

44
00:01:59,230 --> 00:02:02,380
מושך מאיטרטיבי
גרסה של זה, ש

45
00:02:02,380 --> 00:02:05,010
אנחנו גם נסתכל ברגע.

46
00:02:05,010 --> 00:02:08,310
>> אז הנה כמה
משחק מילים facts-- intended--

47
00:02:08,310 --> 00:02:10,169
על factorial--
פונקצית עצרת.

48
00:02:10,169 --> 00:02:13,090
העצרת של 1, כפי שאמרתי, היא 1.

49
00:02:13,090 --> 00:02:15,690
העצרת של 2 היא 2 פעמים 1.

50
00:02:15,690 --> 00:02:18,470
העצרת של 3 היא 3
פעמים 2 פעמים 1, וכן הלאה.

51
00:02:18,470 --> 00:02:20,810
דברנו על 4 ו -5 כבר.

52
00:02:20,810 --> 00:02:23,940
>> אבל מסתכל על זה, זה לא זה נכון?

53
00:02:23,940 --> 00:02:28,220
לא עצרת של 2 רק
2 פעמים העצרת של 1?

54
00:02:28,220 --> 00:02:31,130
אני מתכוון, את העצרת של 1 היא 1.

55
00:02:31,130 --> 00:02:34,940
אז למה אנחנו לא יכולים פשוט להגיד את זה,
מאז עצרת של 2 היא 2 פעמים 1,

56
00:02:34,940 --> 00:02:38,520
רק 2 פעמים זה באמת
העצרת של 1?

57
00:02:38,520 --> 00:02:40,900
>> ולאחר מכן הרחבת רעיון ש,
לא העצרת של 3

58
00:02:40,900 --> 00:02:44,080
3 פעמים את העצרת של 2 רק?

59
00:02:44,080 --> 00:02:50,350
והעצרת של 4 היא 4 פעמים
העצרת של 3, וכן הלאה?

60
00:02:50,350 --> 00:02:52,530
למעשה, את העצרת
רק של כל מספר יכול

61
00:02:52,530 --> 00:02:54,660
לבוא לידי ביטוי אם סוג
של לשאת את זה לנצח.

62
00:02:54,660 --> 00:02:56,870
אנחנו סוג של יכולים להכליל
הבעיה העצרת

63
00:02:56,870 --> 00:02:59,910
כמו שזה n פעמים
עצרת של n מינוס 1.

64
00:02:59,910 --> 00:03:04,840
זה n פעמים התוצר של
כל המספרים פחות ממני.

65
00:03:04,840 --> 00:03:08,890
>> רעיון זה, זה
הכללה של הבעיה,

66
00:03:08,890 --> 00:03:13,410
מאפשר לנו באופן רקורסיבי
להגדיר את פונקצית העצרת.

67
00:03:13,410 --> 00:03:15,440
כאשר אתה מגדיר את פונקציה
באופן רקורסיבי, יש

68
00:03:15,440 --> 00:03:17,470
שני דברים שצריך להיות חלק ממנה.

69
00:03:17,470 --> 00:03:20,990
אתה צריך משהו שנקרא
מקרה בסיס, אשר, כאשר אתה מפעיל אותו,

70
00:03:20,990 --> 00:03:22,480
יהיה לעצור את התהליך רקורסיבית.

71
00:03:22,480 --> 00:03:25,300
>> אחרת, פונקציה שקוראת
עצמו-- כפי שאתה עלול imagine--

72
00:03:25,300 --> 00:03:26,870
יכול להימשך לנצח.

73
00:03:26,870 --> 00:03:29,047
פונקציה קוראת לפונקציה
קורא קריאות הפונקציה

74
00:03:29,047 --> 00:03:30,380
הפונקציה קוראת לפונקציה.

75
00:03:30,380 --> 00:03:32,380
אם אין לך דרך
כדי לעצור את זה, התכנית שלך

76
00:03:32,380 --> 00:03:34,760
יהיה תקוע ביעילות
בלולאה אינסופית.

77
00:03:34,760 --> 00:03:37,176
זה יתרסק סופו של דבר,
כי זה ייגמר זיכרון.

78
00:03:37,176 --> 00:03:38,990
אבל זה לא לעניין.

79
00:03:38,990 --> 00:03:42,210
>> אנחנו צריכים בדרך אחרת כדי לעצור
דברים מלבד מתרסק התכנית שלנו,

80
00:03:42,210 --> 00:03:46,010
כי תכנית שמתרסקת היא
כנראה לא יפה או אלגנטי.

81
00:03:46,010 --> 00:03:47,690
וכך אנו קוראים לזה מקרה הבסיס.

82
00:03:47,690 --> 00:03:50,610
זהו פתרון פשוט
לבעיה אשר עוצרת

83
00:03:50,610 --> 00:03:52,770
התהליך רקורסיבית התרחשות.

84
00:03:52,770 --> 00:03:55,220
אז זה חלק אחד של
פונקציה רקורסיבית.

85
00:03:55,220 --> 00:03:56,820
>> החלק השני הוא המקרה רקורסיבית.

86
00:03:56,820 --> 00:03:59,195
וזה מקום שבי רקורסיה
יהיה למעשה להתקיים.

87
00:03:59,195 --> 00:04:02,200
זה מקום שבי
פונקציה לקרוא לעצמה.

88
00:04:02,200 --> 00:04:05,940
>> זה לא לקרוא לעצמה בדיוק
באותו אופן שזה נקרא.

89
00:04:05,940 --> 00:04:08,880
זה יהיה וריאציה קלה
שהופך את הבעיה זה

90
00:04:08,880 --> 00:04:11,497
מנסה לפתור קצת קטנטן קטן יותר.

91
00:04:11,497 --> 00:04:14,330
אבל זה בדרך כלל עובר באק
לפתור את חלק הארי של הפתרון

92
00:04:14,330 --> 00:04:17,450
לקריאה שונה לאורך הקו.

93
00:04:17,450 --> 00:04:20,290
>> איזו ממראה של אלה
כמו במקרה הבסיס כאן?

94
00:04:20,290 --> 00:04:25,384
שאחד מאלה נראה כמו
פתרון הפשוט לבעיה?

95
00:04:25,384 --> 00:04:27,550
יש לנו חבורה של עצרות,
ואנחנו יכולים להמשיך

96
00:04:27,550 --> 00:04:30,470
הולך on-- 6, 7, 8, 9, 10, וכן הלאה.

97
00:04:30,470 --> 00:04:34,130
>> אבל אחד מאלה נראה כמו
מקרה טוב להיות מקרה הבסיס.

98
00:04:34,130 --> 00:04:35,310
זה פתרון פשוט מאוד.

99
00:04:35,310 --> 00:04:37,810
אנחנו לא צריכים לעשות שום דבר מיוחד.

100
00:04:37,810 --> 00:04:40,560
>> העצרת של 1 היא רק 1.

101
00:04:40,560 --> 00:04:42,790
אנחנו לא צריכים לעשות שום
כפל בכל.

102
00:04:42,790 --> 00:04:45,248
זה נראה כמו אם אנחנו הולכים
כדי לנסות ולפתור את הבעיה הזו,

103
00:04:45,248 --> 00:04:47,600
ואנחנו צריכים להפסיק
רקורסיה איפשהו,

104
00:04:47,600 --> 00:04:50,610
אנחנו כנראה רוצים להפסיק
זה כשנגיע ל1.

105
00:04:50,610 --> 00:04:54,580
אנחנו לא רוצים לעצור לפני ש.

106
00:04:54,580 --> 00:04:56,660
>> אז אם אנחנו מגדירים
פונקצית העצרת שלנו,

107
00:04:56,660 --> 00:04:58,690
הנה שלד ל
איך אנחנו יכולים לעשות את זה.

108
00:04:58,690 --> 00:05:03,110
אנחנו צריכים לחבר את שני אלה things--
מקרה הבסיס והמקרה רקורסיבית.

109
00:05:03,110 --> 00:05:04,990
מה מקרה הבסיס?

110
00:05:04,990 --> 00:05:10,150
אם n הוא שווה ל 1, לחזור 1-- זה
בעיה ממש פשוטה לפתרון.

111
00:05:10,150 --> 00:05:11,890
>> העצרת של 1 היא 1.

112
00:05:11,890 --> 00:05:13,860
זה שום דבר לא 1 פעמים.

113
00:05:13,860 --> 00:05:15,020
זה רק 1.

114
00:05:15,020 --> 00:05:17,170
זוהי עובדה קלה מאוד.

115
00:05:17,170 --> 00:05:19,620
וכך זה יכול להיות מקרה הבסיס שלנו.

116
00:05:19,620 --> 00:05:24,730
אם אנחנו מקבלים עברנו 1 לזה
פונקציה, אנחנו פשוט לחזור 1.

117
00:05:24,730 --> 00:05:27,320
>> מה רקורסיבית
מקרה כנראה נראה?

118
00:05:27,320 --> 00:05:32,445
לכל מספר אחר
מלבד 1, מה הדפוס?

119
00:05:32,445 --> 00:05:35,780
ובכן, אם אנחנו לוקחים
העצרת של n,

120
00:05:35,780 --> 00:05:38,160
זה הפעמים n העצרת של n מינוס 1.

121
00:05:38,160 --> 00:05:42,130
>> אם אנחנו לוקחים את העצרת של 3,
זה 3 פעמים את העצרת של 3 מינוס 1,

122
00:05:42,130 --> 00:05:43,070
או 2.

123
00:05:43,070 --> 00:05:47,330
ולכן אם אנחנו לא
מסתכל על 1, אחרת

124
00:05:47,330 --> 00:05:51,710
פעמים n התמורה
עצרת של n מינוס 1.

125
00:05:51,710 --> 00:05:53,210
זה די פשוט.

126
00:05:53,210 --> 00:05:57,360
>> ולמען שיש מעט
מנקה ועוד קוד אלגנטי,

127
00:05:57,360 --> 00:06:01,440
יודע שאם יש לנו לולאות של שורה אחת
או שורה אחת סניפים מותנים,

128
00:06:01,440 --> 00:06:04,490
אנחנו יכולים להיפטר מכל של
סוגריים מסולסלים סביבם.

129
00:06:04,490 --> 00:06:06,850
אז אנחנו יכולים לאחד את זה לזה.

130
00:06:06,850 --> 00:06:09,640
זה יש בדיוק את אותו
פונקציונלי כמו זה.

131
00:06:09,640 --> 00:06:13,850
>> אני רק לוקח מן מתולתל
פלטה, כי יש רק קו אחד

132
00:06:13,850 --> 00:06:18,500
בתוך סניפים מותנים אלה.

133
00:06:18,500 --> 00:06:21,160
אז אלה מתנהגים באופן זהה.

134
00:06:21,160 --> 00:06:23,800
אם n הוא שווה ל 1, 1 חזור.

135
00:06:23,800 --> 00:06:28,351
אחרת לחזור פעמים n
העצרת של n מינוס 1.

136
00:06:28,351 --> 00:06:29,850
אז אנחנו עושים את הבעיה קטנה יותר.

137
00:06:29,850 --> 00:06:33,850
אם n מתחיל כ5, אנחנו הולכים
לחזור 5 פעמים את העצרת של 4.

138
00:06:33,850 --> 00:06:37,100
ואנו רואים בדקות כאשר אנו מדברים
על stack-- השיחה בוידאו אחר

139
00:06:37,100 --> 00:06:39,390
שבו אנחנו מדברים על
קורא stack-- נלמד

140
00:06:39,390 --> 00:06:41,630
על למה בדיוק את התהליך הזה עובד.

141
00:06:41,630 --> 00:06:46,970
>> אבל בעוד עצרת של 5 אומרת
לחזור 5 פעמים עצרת של 4, ו -4

142
00:06:46,970 --> 00:06:49,710
הוא הולך להגיד, בסדר, טוב, תמורה
4 פעמים העצרת של 3.

143
00:06:49,710 --> 00:06:51,737
וכמו שאתם יכולים לראות, אנחנו
סוג של התקרבות 1.

144
00:06:51,737 --> 00:06:53,820
אנחנו מתקרבים ו
קרוב יותר לזה מקרה בסיס.

145
00:06:53,820 --> 00:06:58,180
>> וברגע שאנחנו מכים את מקרה הבסיס,
כל הפונקציות הקודמות

146
00:06:58,180 --> 00:07:00,540
יש תשובה שהם מחפשים.

147
00:07:00,540 --> 00:07:03,900
עצרת של 2 אמרה תמורה
2 פעמים העצרת של 1.

148
00:07:03,900 --> 00:07:06,760
ובכן, עצרת של 1 מחזירה 1.

149
00:07:06,760 --> 00:07:10,090
אז הקריאה לעצרת
של 2 יכול לחזור 2 פעמים 1,

150
00:07:10,090 --> 00:07:13,980
ולהחזיר את זה לעצרת של
3, שמחכה לתוצאה ש.

151
00:07:13,980 --> 00:07:17,110
>> ואז זה יכול לחשב
התוצאה, 3 פעמיה 2 היא 6,

152
00:07:17,110 --> 00:07:18,907
ולהחזיר אותו לעצרת של 4.

153
00:07:18,907 --> 00:07:20,740
ושוב, יש לנו
וידאו בשיחת הערימה

154
00:07:20,740 --> 00:07:23,810
איפה זה בא לידי ביטוי קטן
יותר ממה שאני אומר עכשיו.

155
00:07:23,810 --> 00:07:25,300
אבל זהו זה.

156
00:07:25,300 --> 00:07:29,300
זה לבד הוא הפתרון ל
חישוב העצרת של מספר.

157
00:07:29,300 --> 00:07:31,527
>> זה רק ארבע שורות של קוד.

158
00:07:31,527 --> 00:07:32,610
זה די מגניב, נכון?

159
00:07:32,610 --> 00:07:35,480
זה סוג של סקסי.

160
00:07:35,480 --> 00:07:38,580
>> אז באופן כללי, אבל לא
תמיד, פונקציה רקורסיבית

161
00:07:38,580 --> 00:07:41,190
יכול להחליף לולאה ב
פונקציה שאינה רקורסיבית.

162
00:07:41,190 --> 00:07:46,100
אז הנה, זה לצד זה, הוא איטרטיבי
גרסה של פונקצית העצרת.

163
00:07:46,100 --> 00:07:49,650
שניהם לחשב אלה
בדיוק אותו הדבר.

164
00:07:49,650 --> 00:07:52,170
>> שניהם לחשב העצרת של n.

165
00:07:52,170 --> 00:07:54,990
הגרסה משמאל
משתמש רקורסיה לעשות את זה.

166
00:07:54,990 --> 00:07:58,320
הגרסה מהימין
משתמש איטרציה לעשות את זה.

167
00:07:58,320 --> 00:08:02,050
>> והודעה, אנחנו צריכים להכריז
מוצר שלם משתנה.

168
00:08:02,050 --> 00:08:02,940
ואז אנחנו לולאה.

169
00:08:02,940 --> 00:08:06,790
כל עוד n הוא גדול מ -0, אנחנו
הולך ומתרבה שמוצר על ידי n

170
00:08:06,790 --> 00:08:09,890
וdecrementing n עד
אנו מחשבים את המוצר.

171
00:08:09,890 --> 00:08:14,600
אז שני תפקידים אלה, שוב,
לעשות בדיוק את אותו הדבר.

172
00:08:14,600 --> 00:08:19,980
אבל הם לא עושים את זה ב
בדיוק באותו אופן.

173
00:08:19,980 --> 00:08:22,430
>> עכשיו, זה אפשרי
יש בסיס אחד או יותר

174
00:08:22,430 --> 00:08:25,770
מקרה או יותר מאחד
מקרה רקורסיבית, בהתאם

175
00:08:25,770 --> 00:08:27,670
על מה הפונקציה שלך מנסה לעשות.

176
00:08:27,670 --> 00:08:31,650
אתה לא בהכרח מוגבל רק ל
מקרה בסיס יחיד או רקורסיבית אחת

177
00:08:31,650 --> 00:08:32,370
כיסוי מגן.

178
00:08:32,370 --> 00:08:35,320
אז דוגמא של משהו
במקרים רבים בסיס

179
00:08:35,320 --> 00:08:37,830
יכול להיות זה--
רצף פיבונאצ'י.

180
00:08:37,830 --> 00:08:41,549
>> אולי אתה זוכר מ
ימי בית ספר יסודיים

181
00:08:41,549 --> 00:08:45,740
שרצף פיבונאצ'י מוגדר
כמו זה-- האלמנט הראשון הוא 0.

182
00:08:45,740 --> 00:08:46,890
האלמנט השני הוא 1.

183
00:08:46,890 --> 00:08:49,230
שני אלה הם רק על ידי הגדרה.

184
00:08:49,230 --> 00:08:55,920
>> אז כל אלמנט אחר מוגדר
כסכום של n מינוס 1 ומינוס 2 n.

185
00:08:55,920 --> 00:09:00,330
אז האלמנט השלישי
יהיה 0 בתוספת 1 הוא 1.

186
00:09:00,330 --> 00:09:03,280
ואז האלמנט הרביעי
יהיה האלמנט השני, 1,

187
00:09:03,280 --> 00:09:06,550
בתוספת האלמנט השלישי, 1.

188
00:09:06,550 --> 00:09:08,507
וזה יהיה 2.

189
00:09:08,507 --> 00:09:09,340
וכן הלאה וכן הלאה.

190
00:09:09,340 --> 00:09:11,680
>> אז במקרה הזה, יש לנו שני מקרי בסיס.

191
00:09:11,680 --> 00:09:14,850
אם n הוא שווה ל 1, 0 לחזור.

192
00:09:14,850 --> 00:09:18,560
אם n הוא שווה ל 2, 1 חזור.

193
00:09:18,560 --> 00:09:25,930
אחרת, תחזור פיבונאצ'י של n
מינוס 1 בתוספת פיבונאצ'י של n מינוס 2.

194
00:09:25,930 --> 00:09:27,180
>> אז זה מקרי בסיס מרובים.

195
00:09:27,180 --> 00:09:29,271
מה לגבי מקרים רקורסיבית מרובים?

196
00:09:29,271 --> 00:09:31,520
ובכן, יש משהו
נקרא השערת Collatz.

197
00:09:31,520 --> 00:09:34,630
אני לא הולך להגיד,
אתה יודע מה זה,

198
00:09:34,630 --> 00:09:38,170
כי זה בעצם סופי שלנו
בעיה לוידאו המסוים הזה.

199
00:09:38,170 --> 00:09:43,220
וזה התרגיל שלנו
לעבוד עליהם יחד.

200
00:09:43,220 --> 00:09:46,760
>> אז הנה מה ש
השערת קולץ הוא--

201
00:09:46,760 --> 00:09:48,820
הוא חל על כל מספר שלם חיובי.

202
00:09:48,820 --> 00:09:51,500
וזה משער שזה
תמיד אפשר לחזור

203
00:09:51,500 --> 00:09:55,060
1 אם אתה בצע את הפעולות הבאות.

204
00:09:55,060 --> 00:09:57,560
אם n הוא 1, לעצור.

205
00:09:57,560 --> 00:10:00,070
יש לנו חזרה ל1 אם n הוא 1.

206
00:10:00,070 --> 00:10:05,670
>> אחרת, לעבור את זה
תהליך שוב על n מתחלק ב -2.

207
00:10:05,670 --> 00:10:08,200
ולראות אם אתה יכול לחזור ל1.

208
00:10:08,200 --> 00:10:13,260
אחרת, אם n הוא מוזר, לעבור
תהליך זה שוב על 3 יד בתוספת 1,

209
00:10:13,260 --> 00:10:15,552
או 3 פעמים n בתוספת 1.

210
00:10:15,552 --> 00:10:17,010
אז הנה יש לנו מקרה בסיס יחיד.

211
00:10:17,010 --> 00:10:18,430
אם n הוא שווה ל 1, לעצור.

212
00:10:18,430 --> 00:10:20,230
אנחנו לא עושים שום רקורסיה יותר.

213
00:10:20,230 --> 00:10:23,730
>> אבל יש לנו שני מקרים רקורסיבית.

214
00:10:23,730 --> 00:10:28,750
אם n הוא גם, שאנחנו עושים רקורסיבית אחת
מקרה, קורא מחולק n על ידי 2.

215
00:10:28,750 --> 00:10:33,950
אם n הוא מוזר, אנחנו עושים שונים
מקרה רקורסיבית על 3 פעמים n בתוספת 1.

216
00:10:33,950 --> 00:10:39,120
>> ולכן המטרה של סרטון זה היא
לקחת שני, להשהות את הווידאו,

217
00:10:39,120 --> 00:10:42,440
ולנסות ולכתוב את זה
פונקציה רקורסיבית Collatz

218
00:10:42,440 --> 00:10:47,640
שבו אתה עובר בn ערך, ו
היא מחשבת כמה צעדיה

219
00:10:47,640 --> 00:10:52,430
לוקח להגיע ל1 אם אתה מתחיל מn
ואתה מבצע את הפעולות האלה למעלה.

220
00:10:52,430 --> 00:10:56,660
אם n הוא 1, זה לוקח 0 צעדים.

221
00:10:56,660 --> 00:11:00,190
אחרת, זה הולך
לקחת צעד אחד ועוד עם זאת

222
00:11:00,190 --> 00:11:06,200
צעדים רבים שנדרש משני n
חלקי 2 אם n הוא גם, או 3 יד בתוספת 1

223
00:11:06,200 --> 00:11:08,100
אם n הוא מוזר.

224
00:11:08,100 --> 00:11:11,190
>> עכשיו, אני כבר לשים על המסך כאן
כמה דברים בדיקה בשבילך,

225
00:11:11,190 --> 00:11:15,690
כמה מקרי בדיקות בשבילך, כדי לראות
מה אלה מספרי Collatz השונים,

226
00:11:15,690 --> 00:11:17,440
וגם איור
של הצעדים ש

227
00:11:17,440 --> 00:11:20,390
צריך להיות עבר כל כך אתה יכול
סוג של לראות את התהליך הזה בפעולה.

228
00:11:20,390 --> 00:11:24,222
אז אם n שווה ל
1, Collatz של n הוא 0.

229
00:11:24,222 --> 00:11:26,180
אתה לא צריך לעשות
דבר לחזור ל1.

230
00:11:26,180 --> 00:11:27,600
אתה כבר שם.

231
00:11:27,600 --> 00:11:30,550
>> אם n הוא 2, זה לוקח
צעד אחד כדי להגיע ל1.

232
00:11:30,550 --> 00:11:31,810
אתה מתחיל עם 2.

233
00:11:31,810 --> 00:11:33,100
ובכן, 2 הוא לא שווה ל 1.

234
00:11:33,100 --> 00:11:36,580
אז זה הולך להיות צעד אחד
בתוספת עם זאת רבים צעדיו

235
00:11:36,580 --> 00:11:38,015
לוקח על מחולק n על ידי 2.

236
00:11:38,015 --> 00:11:41,280

237
00:11:41,280 --> 00:11:42,910
>> 2 מחולקים 2 הוא 1.

238
00:11:42,910 --> 00:11:47,200
אז זה לוקח צעד אחד ועוד עם זאת
צעדים רבים שלוקח ל1.

239
00:11:47,200 --> 00:11:49,720
1 לוקח אפס צעדים.

240
00:11:49,720 --> 00:11:52,370
>> במשך 3, כפי שניתן לראות, יש
לא מעט שלבים כרוכים.

241
00:11:52,370 --> 00:11:53,590
אתה הולך מ 3.

242
00:11:53,590 --> 00:11:56,710
ואז אתה הולך ל
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
זה לוקח שבעה צעדים כדי לחזור ל1.

244
00:11:58,804 --> 00:12:01,220
וכמו שאתה יכול לראות, יש
כמה מקרי מבחן אחרים כאן

245
00:12:01,220 --> 00:12:02,470
כדי לבדוק את התכנית שלך.

246
00:12:02,470 --> 00:12:03,970
אז שוב, להשהות את הווידאו.

247
00:12:03,970 --> 00:12:09,210
ואני אלך עכשיו לקפוץ חזרה ל
מה התהליך בפועל הוא כאן,

248
00:12:09,210 --> 00:12:11,390
מה היא השערה זו.

249
00:12:11,390 --> 00:12:14,140
>> תראה אם ​​אתה יכול להבין
איך להגדיר Collatz של n

250
00:12:14,140 --> 00:12:19,967
כך שהיא מחשבת כמה
צעדים שנדרש כדי להגיע ל1.

251
00:12:19,967 --> 00:12:23,050
אז אני מקווה, שעצרת את הווידאו
ואתה לא רק מחכה לי

252
00:12:23,050 --> 00:12:25,820
כדי לתת לך את התשובה כאן.

253
00:12:25,820 --> 00:12:29,120
אבל אם אתה, גם,
הנה התשובה בכל מקרה.

254
00:12:29,120 --> 00:12:33,070
>> אז הנה הגדרה אפשרית
של פונקצית Collatz.

255
00:12:33,070 --> 00:12:35,610
הבסיס שלנו case-- אם n הוא
שווה ל -1, אנו חוזרים 0.

256
00:12:35,610 --> 00:12:38,250
זה לא לוקח כל
צעדים כדי לחזור ל1.

257
00:12:38,250 --> 00:12:42,710
>> אחרת, יש לנו שתי cases-- רקורסיבית
אחד מספרים אפילו ואחד למוזר.

258
00:12:42,710 --> 00:12:47,164
דרכי לבדוק למספרים אפילו
הוא לבדוק אם n mod 2 שווה 0.

259
00:12:47,164 --> 00:12:49,080
זהו בעצם, שוב,
שואל את השאלה,

260
00:12:49,080 --> 00:12:54,050
אם אתה זוכר מה הוא-- mod אם אני
n הפרד על ידי 2 שאין שארית?

261
00:12:54,050 --> 00:12:55,470
זה יהיה גם מספר.

262
00:12:55,470 --> 00:13:01,370
>> ולכן אם n mod 2 שווה 0 הוא
בדיקה היא זה אפילו מספר.

263
00:13:01,370 --> 00:13:04,250
אם כך, אני רוצה לחזור 1,
כי זה בהחלט

264
00:13:04,250 --> 00:13:09,270
לוקח צעד אחד בתוספת של Collatz
מה מספר הוא חצי ממני.

265
00:13:09,270 --> 00:13:13,910
אחרת, אני רוצה לחזור 1
בתוספת 3 פעמים Collatz של n בתוספת 1.

266
00:13:13,910 --> 00:13:16,060
זה היה אחר
צעד רקורסיבית ש

267
00:13:16,060 --> 00:13:19,470
יכול לקחת כדי לחשב את
Collatz-- מספר הצעדים

268
00:13:19,470 --> 00:13:22,610
שנדרש כדי לחזור
עד 1 ניתנה מספר.

269
00:13:22,610 --> 00:13:24,610
אז אני מקווה, דוגמא זו
נתתי לך קצת

270
00:13:24,610 --> 00:13:26,620
של טעם של נהלים רקורסיבית.

271
00:13:26,620 --> 00:13:30,220
יש לקוות, אתה חושב קוד הוא
קצת יותר יפה אם ייושם

272
00:13:30,220 --> 00:13:32,760
בדרך אלגנטית, רקורסיבית.

273
00:13:32,760 --> 00:13:35,955
אבל גם אם לא, רקורסיה היא
כלי באמת חזק בכל זאת.

274
00:13:35,955 --> 00:13:38,330
ואז זה בהחלט משהו
כדי לקבל את הראש שלך בסביבה,

275
00:13:38,330 --> 00:13:41,360
כי אתה יכול ליצור
תוכניות די מגניבים באמצעות רקורסיה

276
00:13:41,360 --> 00:13:45,930
כי אחר עלולים להיות מורכב לכתוב
אם אתה משתמש בלולאות ואיטרציה.

277
00:13:45,930 --> 00:13:46,980
אני דאג לויד.

278
00:13:46,980 --> 00:13:48,780
זה CS50.

279
00:13:48,780 --> 00:13:50,228