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
მაგრამ დღეს, ჩვენ ვაპირებთ ფოკუსირება
on რეკურსიული ფუნქციები.

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, რომ
იღებს ერთი string როგორც შეყვანის და

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
ჩვენ შეგვიძლია წარმოადგენს ამ რეკურსიული
დარეკეთ ამ ფორთოხლის arrow

21
00:01:09,610 --> 00:01:11,360
looping უკან თავად.

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
ამ ფუნქციას, hi, ბათილად ფუნქცია
რომ იღებს int n, როგორც შეყვანის.

31
00:01:39,610 --> 00:01:41,260
ბაზის შემთხვევაში მოდის პირველი.

32
00:01:41,260 --> 00:01:46,220
თუ n ნაკლებია, ვიდრე ნულოვანი, ბეჭდვითი bye და
დაბრუნდეს ყველა სხვა შემთხვევაში,

33
00:01:46,220 --> 00:01:49,400
ფუნქცია ბეჭდვა hi და შეასრულოს
რეკურსიული ზარი.

34
00:01:49,400 --> 00:01:53,600
სხვა ზარი ფუნქცია hi ერთად
decremented შეყვანის ღირებულება.

35
00:01:53,600 --> 00:01:56,790
>> ახლა, მიუხედავად იმისა, რომ ჩვენ ბეჭდვა hi,
ფუნქცია არ შეწყვიტოს სანამ ჩვენ

36
00:01:56,790 --> 00:02:00,370
დაიბრუნებს დაბრუნების ტიპის,
ამ შემთხვევაში ბათილად.

37
00:02:00,370 --> 00:02:04,830
ასე რომ, ყოველ n გარდა ბაზის შემთხვევაში,
ამ ფუნქციის hi დაბრუნდება hi

38
00:02:04,830 --> 00:02:06,890
of 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
ასე მოუწოდებდა hi (3) ბეჭდვა hi და
შეასრულოს hi (2), რომელიც ახორციელებს hi (1) ერთი

42
00:02:16,960 --> 00:02:20,560
რომელიც ახორციელებს hi (0), სადაც
ბაზის შემთხვევაში მდგომარეობა დაკმაყოფილებულია.

43
00:02:20,560 --> 00:02:24,100
ასე რომ, hi (0) ბეჭდავს bye და ანაზღაურება.

44
00:02:24,100 --> 00:02:24,990
>> OK.

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
>> მოდით შევხედოთ factorial
ოპერაცია გამოიყენება ყველაზე ხშირად

50
00:02:41,340 --> 00:02:43,660
ალბათობა გათვლები.

51
00:02:43,660 --> 00:02:48,120
Factorial of n არის პროდუქტი ყველა
დადებითი მთელი რიცხვი ნაკლები

52
00:02:48,120 --> 00:02:49,400
და ტოლია n.

53
00:02:49,400 --> 00:02:56,731
ასე რომ factorial ხუთ არის 5 ჯერ 4 ჯერ
3 ჯერ 2 ჯერ 1 მისცეს 120.

54
00:02:56,731 --> 00:03:01,400
ოთხი factorial არის 4 ჯერ 3 ჯერ
2 ჯერ 1 რათა 24.

55
00:03:01,400 --> 00:03:04,910
და იგივე წესი ვრცელდება
ნებისმიერი დადებითი მთელი რიცხვი.

56
00:03:04,910 --> 00:03:08,670
>> ასე როგორ შეიძლება ჩვენ წერენ რეკურსიული
ფუნქცია, რომელიც ითვლის factorial

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 factorial
მოიცავს გამრავლებით 4 3 2 1

63
00:03:30,270 --> 00:03:33,010
და რომ იმავე გამრავლება
გამოჩენას აქ,

64
00:03:33,010 --> 00:03:35,430
განმარტება 4 factorial.

65
00:03:35,430 --> 00:03:39,810
ასე რომ, ჩვენ ვხედავთ, რომ 5 factorial არის
მხოლოდ 5 ჯერ 4 factorial.

66
00:03:39,810 --> 00:03:43,360
ახლა ჯერ ეს ნიმუში ვრცელდება
4 factorial ისევე?

67
00:03:43,360 --> 00:03:44,280
დიახ.

68
00:03:44,280 --> 00:03:49,120
ჩვენ ვხედავთ, რომ 4 factorial შეიცავს
გამრავლება 3 ჯერ 2 ჯერ 1,

69
00:03:49,120 --> 00:03:51,590
იმავე განმარტება 3 factorial.

70
00:03:51,590 --> 00:03:56,950
ასე რომ 4 factorial უდრის 4 ჯერ 3
factorial, და ა.შ. და ა.შ. ჩვენი

71
00:03:56,950 --> 00:04:02,170
ნიმუში ჩხირები წლის 1 factorial, რომელიც
ზოგადად უდრის 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 factorial უდრის n times
factorial of n მინუს 1.

75
00:04:13,260 --> 00:04:14,370
და ჩვენი ბაზის შემთხვევაში?

76
00:04:14,370 --> 00:04:17,370
ეს უბრალოდ ჩვენი განმარტება
1 factorial.

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
factorial of n მინუს 1.

82
00:04:32,180 --> 00:04:33,590
>> ახლა მოდით შეამოწმოთ ეს ჩვენი.

83
00:04:33,590 --> 00:04:35,900
მოდით ცდილობენ factorial 4.

84
00:04:35,900 --> 00:04:39,420
პერ ჩვენი ფუნქცია ის ტოლია
4 ჯერ factorial (3).

85
00:04:39,420 --> 00:04:43,040
Factorial (3) უდრის
3 ჯერ factorial (2).

86
00:04:43,040 --> 00:04:48,700
Factorial (2) უდრის 2 ჯერ
factorial (1), რომელიც დააბრუნებს 1.

87
00:04:48,700 --> 00:04:52,490
Factorial (2) ახლა ბრუნდება 2 ჯერ 1, 2.

88
00:04:52,490 --> 00:04:55,960
Factorial (3) ახლა დაბრუნდნენ
3 ჯერ 2, 6.

89
00:04:55,960 --> 00:05:02,490
და ბოლოს, factorial (4)
ბრუნდება 4 ჯერ, 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> თუ თქვენ encountering ნებისმიერი სირთულის
ერთად რეკურსიული ზარი, ვიტყვი, რომ

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
მაგალითად, თუ მე ვიცი, რომ
factorial (5) შეადგენს 5 ჯერ

95
00:05:18,960 --> 00:05:24,870
factorial (4), მე ვაპირებ, რომ მჯერა, რომ
factorial (4) მომცემს 24.

96
00:05:24,870 --> 00:05:28,510
ვფიქრობ, რომ ეს ცვლადი, თუ
იქნება, რადგან თუ თქვენ უკვე განსაზღვრულია

97
00:05:28,510 --> 00:05:30,070
factorial (4).

98
00:05:30,070 --> 00:05:33,850
ასე რომ, ნებისმიერი factorial (n), ეს
პროდუქტი n და

99
00:05:33,850 --> 00:05:35,360
წინა factorial.

100
00:05:35,360 --> 00:05:38,130
და ეს წინა factorial
მიღებული მოუწოდებს

101
00:05:38,130 --> 00:05:41,330
factorial of 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
სტრუქტურა ორობითი ძებნა
ხე lends თავად კარგად

127
00:07:04,510 --> 00:07:05,940
to რეკურსიული ძებნა.

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
რომ არ არსებობს კვანძების
დარჩა, რომ sub-ხე.

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, ეწოდება მარცხენა
sub-tree პირველი, ისე მარცხენა კვანძის

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.

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
>> ამ ფუნქციას, hi,
ბათილად ფუნქცია, რომელიც იღებს

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, ბეჭდვითი
"Bye" და სანაცვლოდ.

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