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
कार्यक्रम के डिजाइन का मतलब प्रत्यावर्तन के बाद
आप आत्म referential है कि

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 लेता है.

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
तो हर 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
और एन के बराबर.

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 भाज्य देखना
1 से 2 से 3 से 4 गुणा शामिल

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 के भाज्य शून्य से 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
फिर पुनरावर्ती कॉल पर चलती है,
हम एन बार वापस कर देंगे

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 के उत्पाद और

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
कि एक पूर्णांक लेता है और रिटर्न
सभी लगातार सकारात्मक का योग

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
आप एक पहचान कर सकते हैं
राशि (एन) के लिए पैटर्न.

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
>> Recursion एक बहुत शक्तिशाली उपकरण है,
इसलिए निश्चित रूप से यह करने के लिए सीमित नहीं है

119
00:06:38,040 --> 00:06:39,820
गणितीय कार्य करता है.

120
00:06:39,820 --> 00:06:44,040
Recursion बहुत प्रभावी ढंग से इस्तेमाल किया जा सकता है
उदाहरण के लिए पेड़ों के साथ काम करते हैं.

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
एक अशक्त नोड कारणों के आधार मामले
समारोह का संकेत है, वापस जाने के लिए

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
1 और foo को फिर नियत किया जाएगा
कि नोड के बच्चों पर कहा जा,

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 को reassigned.

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
>> Recursion बहुत शक्तिशाली है और नहीं करने के लिए है
सुरुचिपूर्ण उल्लेख है, लेकिन यह एक हो सकता है

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
एन 0 से कम, प्रिंट है तो
"अलविदा" और बदले.

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