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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Aby zrozumieć
rekurencja, należy

3
00:00:10,190 --> 00:00:13,820
najpierw zrozumieć rekurencję.

4
00:00:13,820 --> 00:00:17,280
Mając rekursji w programie środków projektowych
że masz samozwrotny

5
00:00:17,280 --> 00:00:18,570
definicje.

6
00:00:18,570 --> 00:00:21,520
Rekurencyjne struktury danych, na przykład
są struktury danych, które

7
00:00:21,520 --> 00:00:23,990
zawierać się w
ich definicje.

8
00:00:23,990 --> 00:00:27,160
Ale dziś, mamy zamiar skupić się
na funkcji rekurencyjnych.

9
00:00:27,160 --> 00:00:31,160
>> Przypomnijmy, że funkcje się wejść,
argumenty i zwraca wartość, jak ich

10
00:00:31,160 --> 00:00:34,480
reprezentowane przez wyjście
ten schemat tutaj.

11
00:00:34,480 --> 00:00:38,060
Będziemy myśleć o polu jako ciało
Funkcja, zawierający zestaw

12
00:00:38,060 --> 00:00:42,340
instrukcje, które interpretują
wejściowego i dostarczania sygnału wyjściowego.

13
00:00:42,340 --> 00:00:45,660
Bliższe spojrzenie wewnątrz ciała
Funkcja może ujawnić połączeń do

14
00:00:45,660 --> 00:00:47,430
innych funkcji, jak również.

15
00:00:47,430 --> 00:00:51,300
Weź tę prostą funkcję, Foo, że
przyjmuje pojedynczy ciąg na wejściu i

16
00:00:51,300 --> 00:00:54,630
druki ile liter
że ciąg ma.

17
00:00:54,630 --> 00:00:58,490
Funkcja strlen, na długości łańcucha,
nazywa, którego wyjście jest

18
00:00:58,490 --> 00:01:01,890
wymagane do wywołania printf.

19
00:01:01,890 --> 00:01:05,770
>> Teraz, co sprawia, że ​​funkcji rekurencyjnej
szczególną jest to, że nazywa się.

20
00:01:05,770 --> 00:01:09,610
Możemy reprezentować ten Cykliczne
zadzwonić z tym Orange

21
00:01:09,610 --> 00:01:11,360
pętli z powrotem do siebie.

22
00:01:11,360 --> 00:01:15,630
Ale wykonanie się znowu będzie tylko
dokonać innego wywołanie rekurencyjne, a

23
00:01:15,630 --> 00:01:17,150
drugiego i drugiego.

24
00:01:17,150 --> 00:01:19,100
Ale funkcje rekurencyjne
nie może być nieskończony.

25
00:01:19,100 --> 00:01:23,490
Mają do końca jakoś, czy Twój
Program będzie trwał wiecznie.

26
00:01:23,490 --> 00:01:27,680
>> Więc musimy znaleźć sposób, aby złamać
z połączeń rekurencyjnych.

27
00:01:27,680 --> 00:01:29,900
Nazywamy to wariant podstawowy.

28
00:01:29,900 --> 00:01:33,570
Gdy warunek jest spełniony przypadek bazowy,
Funkcja zwraca bez dokonywania

29
00:01:33,570 --> 00:01:34,950
kolejny wywołanie rekurencyjne.

30
00:01:34,950 --> 00:01:39,610
Weź tę funkcję, hi, funkcję void
że bierze int n jako wejście.

31
00:01:39,610 --> 00:01:41,260
Baza jest pierwszy przypadek.

32
00:01:41,260 --> 00:01:46,220
Jeśli n jest mniejsza od zera, do widzenia i druku
zwrotu dla wszystkich innych przypadkach,

33
00:01:46,220 --> 00:01:49,400
Funkcja drukowania hi i wykonać
wywołanie rekurencyjne.

34
00:01:49,400 --> 00:01:53,600
Innym wywołanie funkcji z hi
zmniejszana wartość wejściowa.

35
00:01:53,600 --> 00:01:56,790
>> Teraz, mimo że drukowanie hi,
funkcja nie zostanie zakończona, dopóki nie

36
00:01:56,790 --> 00:02:00,370
zwraca jego typ zwracany,
w tym przypadku pustki.

37
00:02:00,370 --> 00:02:04,830
Tak więc dla każdego n poza przypadku bazowej
funkcja ta zwróci hi hi

38
00:02:04,830 --> 00:02:06,890
n minus 1.

39
00:02:06,890 --> 00:02:10,050
Ponieważ ta funkcja jest nieaktualna chociaż, my
Nie będzie tu wyraźnie wpisać zwrot.

40
00:02:10,050 --> 00:02:12,000
Musimy tylko wykonać funkcję.

41
00:02:12,000 --> 00:02:16,960
Więc dzwoni hi (3) i będą drukowane hi
wykonać cześć (2), który wykonuje hi (1) jeden

42
00:02:16,960 --> 00:02:20,560
który realizuje hi (0), gdzie
Stan przypadek bazowy jest spełniony.

43
00:02:20,560 --> 00:02:24,100
Więc cześć (0) drukuje do widzenia i wraca.

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

45
00:02:24,990 --> 00:02:28,690
Więc teraz, że mamy zrozumieć podstawy
rekurencyjne funkcje, które są potrzebne

46
00:02:28,690 --> 00:02:32,730
w co najmniej jednym przypadku bazy, jak również
wywołanie rekurencyjne, przejdźmy do

47
00:02:32,730 --> 00:02:34,120
bardziej znaczący przykład.

48
00:02:34,120 --> 00:02:37,830
Jeden, który nie tylko powrót
unieważnić nie wiem co.

49
00:02:37,830 --> 00:02:41,340
>> Rzućmy okiem na silnia
Operacja stosowane najczęściej w

50
00:02:41,340 --> 00:02:43,660
obliczenia prawdopodobieństwa.

51
00:02:43,660 --> 00:02:48,120
Silnia n jest iloczynem co
dodatnią liczbę całkowitą mniejszą

52
00:02:48,120 --> 00:02:49,400
a n równe.

53
00:02:49,400 --> 00:02:56,731
Tak silni pięć jest 5 razy 4 razy
3, 2 razy po 1 i otrzymano 120.

54
00:02:56,731 --> 00:03:01,400
Cztery silnia jest 4 razy 3 razy
2 razy 1 otrzymując 24.

55
00:03:01,400 --> 00:03:04,910
I ma zastosowanie ta sama zasada
do każdej liczby całkowitej.

56
00:03:04,910 --> 00:03:08,670
>> Więc jak możemy napisać rekurencyjną
funkcja, która oblicza silnię

57
00:03:08,670 --> 00:03:09,960
z szeregu?

58
00:03:09,960 --> 00:03:14,700
Cóż, musimy zidentyfikować zarówno
wariant podstawowy i wywołanie rekurencyjne.

59
00:03:14,700 --> 00:03:18,250
Wywołanie rekurencyjne będzie taki sam
we wszystkich przypadkach, z wyjątkiem podstawy

60
00:03:18,250 --> 00:03:21,420
przypadku, co oznacza, że ​​będziemy musieli
znaleźć wzór, który da nam nasze

61
00:03:21,420 --> 00:03:23,350
pożądany wynik.

62
00:03:23,350 --> 00:03:30,270
>> W tym przykładzie, zobacz jak 5 silnia
polega na pomnożeniu 4 na 3 przez 2 do 1

63
00:03:30,270 --> 00:03:33,010
I że sam mnożenie
stwierdzono tutaj

64
00:03:33,010 --> 00:03:35,430
Definicja 4 silnia.

65
00:03:35,430 --> 00:03:39,810
Widzimy więc, że jest 5 silnia
zaledwie 5 razy 4 silnia.

66
00:03:39,810 --> 00:03:43,360
Teraz to ma zastosowanie wzór
do 4 czynnikowych, jak również?

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

68
00:03:44,280 --> 00:03:49,120
Widzimy, że zawiera 4 silnia
mnożenia 3 razy 2 razy 1,

69
00:03:49,120 --> 00:03:51,590
Ta sama definicja jak 3 silnia.

70
00:03:51,590 --> 00:03:56,950
Tak 4 silnia równa się 4 razy 3
silnia i tak dalej, i tak dalej naszym

71
00:03:56,950 --> 00:04:02,170
kije do 1 wzór, który silnia
zgodnie z definicją jest równa 1.

72
00:04:02,170 --> 00:04:04,950
>> Nie ma innego pozytywne
liczbami całkowitymi w lewo.

73
00:04:04,950 --> 00:04:07,870
Mamy więc wzór dla
nasze wywołanie rekurencyjne.

74
00:04:07,870 --> 00:04:13,260
n silnia równa się n razy
silnia n minus 1.

75
00:04:13,260 --> 00:04:14,370
A nasz scenariusz bazowy?

76
00:04:14,370 --> 00:04:17,370
To będzie po prostu nasza definicja
1 silnia.

77
00:04:17,370 --> 00:04:19,995
>> Teraz możemy przejść do pisania
kod funkcji.

78
00:04:19,995 --> 00:04:24,110
Dla przypadku bazowego, musimy
Stan n równa wynosi 1, gdzie

79
00:04:24,110 --> 00:04:25,780
wrócimy 1.

80
00:04:25,780 --> 00:04:29,280
Następnie przejść na cyklicznej rozmowy
wrócimy n razy

81
00:04:29,280 --> 00:04:32,180
silnia n minus 1.

82
00:04:32,180 --> 00:04:33,590
>> Sprawdźmy teraz ten nasz.

83
00:04:33,590 --> 00:04:35,900
Spróbujmy silni 4.

84
00:04:35,900 --> 00:04:39,420
Na naszej funkcji jest równa
do 4 razy silnia (3).

85
00:04:39,420 --> 00:04:43,040
Silnia (3) jest równa
3 razy silnia (2).

86
00:04:43,040 --> 00:04:48,700
Silnia (2) jest równy 2 razy
silnia (1), która zwraca 1.

87
00:04:48,700 --> 00:04:52,490
Silnia (2) zwraca teraz 2 razy 1, 2.

88
00:04:52,490 --> 00:04:55,960
Silnia (3) może teraz powrócić
3 razy 2, 6.

89
00:04:55,960 --> 00:05:02,490
I wreszcie, silnia (4)
zwraca 4 razy 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Jeśli napotykają żadnych trudności
z rekurencyjnego wywołania, udawać, że

91
00:05:06,780 --> 00:05:09,660
funkcja działa już.

92
00:05:09,660 --> 00:05:13,450
Co mam na myśli to, że zalecana
ufać swoim rekurencyjnych wywołań, aby powrócić

93
00:05:13,450 --> 00:05:15,100
odpowiednie wartości.

94
00:05:15,100 --> 00:05:18,960
Na przykład, jeśli wiem, że
silnia (5) wynosi 5 razy

95
00:05:18,960 --> 00:05:24,870
silnia (4), mam nadzieję, że będzie
silnia (4) da mi 24.

96
00:05:24,870 --> 00:05:28,510
Potraktujcie to jako zmienna, jeśli
będzie, jak już określono

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

98
00:05:30,070 --> 00:05:33,850
Więc dla każdego silnia (n), to
Produkt n i

99
00:05:33,850 --> 00:05:35,360
poprzedni silnia.

100
00:05:35,360 --> 00:05:38,130
I ten poprzedni silnia
uzyskuje się przez wywołanie

101
00:05:38,130 --> 00:05:41,330
silnia n minus 1.

102
00:05:41,330 --> 00:05:45,130
>> Teraz, czy można wdrożyć
rekurencyjne funkcjonować samodzielnie.

103
00:05:45,130 --> 00:05:50,490
Załadować do terminala lub run.cs50.net,
i napisz sumę funkcji

104
00:05:50,490 --> 00:05:54,770
że bierze całkowitą n i zwraca
suma wszystkich kolejnych pozytywne

105
00:05:54,770 --> 00:05:57,490
liczby całkowite od 1 do n.

106
00:05:57,490 --> 00:06:01,000
Pisałem z niektórych kwot
Wartości, które pomogą Ci nasza.

107
00:06:01,000 --> 00:06:04,030
Po pierwsze, dowiedzieć się,
Stan przypadek bazowy.

108
00:06:04,030 --> 00:06:06,170
Następnie spojrzeć na sumy (5).

109
00:06:06,170 --> 00:06:09,270
Można wyrazić w kategoriach
innej sumy?

110
00:06:09,270 --> 00:06:11,290
Teraz, co z sumy (4)?

111
00:06:11,290 --> 00:06:15,630
Jak możesz wyrazić sumę (4)
względem innej sumy?

112
00:06:15,630 --> 00:06:19,655
>> Gdy masz sumę (5) i suma (4)
wyrażone w innych sum patrz

113
00:06:19,655 --> 00:06:22,970
Jeśli można zidentyfikować
wzór na sumę (n).

114
00:06:22,970 --> 00:06:26,190
Jeśli nie, spróbuj kilka innych numerów
i wyrazić swoje sumy w

115
00:06:26,190 --> 00:06:28,410
terminy kolejnych numerów.

116
00:06:28,410 --> 00:06:31,930
Poprzez określenie wzorów dla dyskretnych
numery, jesteś na dobrej drodze do

117
00:06:31,930 --> 00:06:34,320
identyfikujący wzorzec dla każdego n.

118
00:06:34,320 --> 00:06:38,040
>> Rekurencja jest bardzo potężnym narzędziem,
tak, oczywiście, że nie ogranicza się do

119
00:06:38,040 --> 00:06:39,820
funkcje matematyczne.

120
00:06:39,820 --> 00:06:44,040
Rekurencja może być używany bardzo skutecznie
w kontaktach z drzew, na przykład.

121
00:06:44,040 --> 00:06:47,210
Sprawdź mało drzew na
bardziej szczegółowy przegląd, ale teraz

122
00:06:47,210 --> 00:06:51,140
Przypomnijmy, że szukanie binarne drzew, w
przede wszystkim składa się z węzłów, z których każda

123
00:06:51,140 --> 00:06:53,820
o wartości i dwoma wskaźnikami węzłów.

124
00:06:53,820 --> 00:06:57,270
Zwykle, jest to reprezentowane przez
Rodzic mający jeden wiersz wskazujący

125
00:06:57,270 --> 00:07:01,870
do lewego i jednego węzła podrzędnego
po prawej węzła podrzędnego.

126
00:07:01,870 --> 00:07:04,510
Struktura poszukiwania binarnego
dobrze nadaje się drzewo

127
00:07:04,510 --> 00:07:05,940
do cyklicznej wyszukiwania.

128
00:07:05,940 --> 00:07:09,730
Wywołanie rekurencyjne, albo przechodzi w
lewy lub prawy węzeł, ale bardziej

129
00:07:09,730 --> 00:07:10,950
o, że w krótkim drzewa.

130
00:07:10,950 --> 00:07:15,690
>> Powiedzmy, że chcesz, aby wykonać operację na
każdy węzeł w binarnym drzewie.

131
00:07:15,690 --> 00:07:17,410
Jak można go o to?

132
00:07:17,410 --> 00:07:20,600
Cóż, można napisać rekurencyjną
Funkcja, która wykonuje operację

133
00:07:20,600 --> 00:07:24,450
na węźle nadrzędnym i sprawia rekurencyjną
zadzwonić do tej samej funkcji,

134
00:07:24,450 --> 00:07:27,630
przechodzącą w lewo i
prawe węzły potomne.

135
00:07:27,630 --> 00:07:31,650
Na przykład, funkcja ta, bla, że
zmienia wartość danego węzła i

136
00:07:31,650 --> 00:07:33,830
wszystkie jego dzieci do 1.

137
00:07:33,830 --> 00:07:37,400
Wariant podstawowy z przyczyn węzłów null
Funkcja powrotu, wskazując

138
00:07:37,400 --> 00:07:41,290
że nie ma żadnych węzłów
w lewo w tym sub-tree.

139
00:07:41,290 --> 00:07:42,620
>> Przejdźmy przez to.

140
00:07:42,620 --> 00:07:44,340
Pierwszy rodzic jest 13.

141
00:07:44,340 --> 00:07:47,930
Zmieniamy wartość na 1, a następnie wywołać
Nasza funkcja po lewej stronie, jak również

142
00:07:47,930 --> 00:07:49,600
w prawo.

143
00:07:49,600 --> 00:07:53,910
Funkcja, bla, nazywa się po lewej
pierwszy podpotok drzewa, tak lewym węzłem

144
00:07:53,910 --> 00:07:57,730
zostanie przeniesiony do 1 i foo
miano na dzieci tego węzła, w

145
00:07:57,730 --> 00:08:01,900
pierwsza w lewo i potem w prawo,
i tak dalej, i tak dalej.

146
00:08:01,900 --> 00:08:05,630
I powiedz im, że nie mają oddziałów
więcej dzieci, więc sam proces

147
00:08:05,630 --> 00:08:09,700
będzie w dalszym ciągu za prawo dzieci
dopóki węzły całego drzewa są

148
00:08:09,700 --> 00:08:11,430
przeniesiony do 1.

149
00:08:11,430 --> 00:08:15,390
>> Jak widać, nie są ograniczone
tylko do jednego wywołanie rekurencyjne.

150
00:08:15,390 --> 00:08:17,930
Tylko tyle, ile będzie to zadanie.

151
00:08:17,930 --> 00:08:21,200
Co jeśli miał drzewa, gdzie każdy
węzeł miał troje dzieci,

152
00:08:21,200 --> 00:08:23,100
Lewy, środkowy i prawy?

153
00:08:23,100 --> 00:08:24,886
Jak można edytować foo?

154
00:08:24,886 --> 00:08:25,860
Cóż, proste.

155
00:08:25,860 --> 00:08:30,250
Wystarczy dodać kolejne połączenie i rekurencyjnej
przechodzą w węzeł środkowy wskaźnika.

156
00:08:30,250 --> 00:08:34,549
>> Rekurencja jest bardzo silny i nie do
wspomnieć, elegancki, ale może być

157
00:08:34,549 --> 00:08:38,010
trudne pojęcie na początku, więc być
pacjenta i nie spiesz się.

158
00:08:38,010 --> 00:08:39,370
Start z przypadku bazowego.

159
00:08:39,370 --> 00:08:42,650
To zazwyczaj najłatwiej zidentyfikować,
i wtedy można pracować

160
00:08:42,650 --> 00:08:43,830
do tyłu stamtąd.

161
00:08:43,830 --> 00:08:46,190
Wiesz, trzeba dotrzeć do
wariant podstawowy, tak, że może

162
00:08:46,190 --> 00:08:47,760
dać kilka wskazówek.

163
00:08:47,760 --> 00:08:53,120
Starają się wyrazić w jeden konkretny przypadek
Terminy pozostałych przypadkach lub w podzbiorów.

164
00:08:53,120 --> 00:08:54,700
>> Dzięki za oglądanie tego krótkie.

165
00:08:54,700 --> 00:08:58,920
Przynajmniej, teraz możesz
rozumieją dowcipy jak ten.

166
00:08:58,920 --> 00:09:01,250
Nazywam się Zamyla, i to jest CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Weź tę funkcję, hi,
void funkcja, która trwa

169
00:09:07,170 --> 00:09:09,212
int n, jako wejście.

170
00:09:09,212 --> 00:09:11,020
Baza jest pierwszy przypadek.

171
00:09:11,020 --> 00:09:14,240
Jeśli n jest mniejsza niż 0, druk
"Do widzenia" i powrót.

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