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
أغتنم هذه وظيفة بسيطة، فو، التي
تأخذ سلسلة واحدة كمدخل و

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
تأخذ هذه الوظيفة، مرحبا، وظيفة الفراغ
أن يأخذ ن الباحث كمدخل.

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
مكالمة أخرى إلى وظيفة مع مرحبا
قيمة المدخلات decremented.

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
لذلك لكل ن بخلاف الحالة الأساسية،
وهذه الوظيفة مرحبا مرحبا العودة

38
00:02:04,830 --> 00:02:06,890
ن ناقص 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
ويساوي ن.

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
ن مضروب يساوي مرات ن
مضروب ن ناقص 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
للقضية الأساس، سيكون لدينا
حالة ن يساوي يساوي 1، حيث

79
00:04:24,110 --> 00:04:25,780
وسوف نعود 1.

80
00:04:25,780 --> 00:04:29,280
ثم الانتقال الى الدعوة متكررة،
وسوف نعود مرة ن

81
00:04:29,280 --> 00:04:32,180
مضروب ن ناقص 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
ذلك لأي مضروب (ن)، انها
المنتج ن و

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
مضروب ن ناقص 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
أعداد صحيحة من ن إلى 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
إذا كان يمكنك تحديد
نمط لمبلغ (ن).

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
تحديد نمط لأي ن.

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
على سبيل المثال، هذه الوظيفة، فو، التي
تغيير قيمة عقدة معينة و

136
00:07:31,650 --> 00:07:33,830
جميع أبنائها إلى 1.

137
00:07:33,830 --> 00:07:37,400
حالة قاعدة من الأسباب عقدة فارغة
وظيفة للعودة، مشيرا إلى

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
يتم استدعاء الدالة، فو، على اليسار
شجرة الفرعية الأولى، وبالتالي فإن العقدة اليسرى

144
00:07:53,910 --> 00:07:57,730
سيتم إعادة تعيين إلى 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
كيف يمكنك تعديل فو؟

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
عدد صحيح، ن، كإدخال.

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