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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Um zu verstehen,
Rekursion, müssen Sie

3
00:00:10,190 --> 00:00:13,820
zuerst verstehen, Rekursion.

4
00:00:13,820 --> 00:00:17,280
Mit Rekursion bei der Programmgestaltung mittels
dass Sie selbst bezogen haben

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

6
00:00:18,570 --> 00:00:21,520
Rekursive Datenstrukturen, zum Beispiel,
sind Datenstrukturen,

7
00:00:21,520 --> 00:00:23,990
schließen sich in
deren Definitionen.

8
00:00:23,990 --> 00:00:27,160
Aber heute werden wir konzentrieren
auf rekursiven Funktionen.

9
00:00:27,160 --> 00:00:31,160
>> Daran erinnern, dass Funktionen übernehmen Eingänge,
Argumente, und einen Wert als

10
00:00:31,160 --> 00:00:34,480
vertreten durch Ausgabe
dieses Diagramm hier.

11
00:00:34,480 --> 00:00:38,060
Wir werden von der Box, da der Körper denken
die Funktion, die die Gruppe der

12
00:00:38,060 --> 00:00:42,340
Anweisungen, die der Interpretation
Eingangs-und ein Ausgangssignal.

13
00:00:42,340 --> 00:00:45,660
Bei näherer Betrachtung innerhalb des Körpers
die Funktion kann Anrufe zu offenbaren,

14
00:00:45,660 --> 00:00:47,430
andere Funktionen.

15
00:00:47,430 --> 00:00:51,300
Nutzen Sie diese einfache Funktion, foo, dass
benötigt ein String als Eingabe und

16
00:00:51,300 --> 00:00:54,630
Drucke wie viele Briefe
dass String hat.

17
00:00:54,630 --> 00:00:58,490
Die Funktion strlen, für String-Länge,
genannt wird, dessen Ausgangssignal

18
00:00:58,490 --> 00:01:01,890
für den Aufruf von printf erforderlich.

19
00:01:01,890 --> 00:01:05,770
>> Nun, was macht eine rekursive Funktion
besondere ist, dass es sich selbst nennt.

20
00:01:05,770 --> 00:01:09,610
Wir können diese rekursive stellen
rufen mit dieser orangefarbenen Pfeil

21
00:01:09,610 --> 00:01:11,360
Schleife zurück zu sich.

22
00:01:11,360 --> 00:01:15,630
Aber selbst wieder ausführen wird nur
eine weitere rekursiven Aufruf und

23
00:01:15,630 --> 00:01:17,150
eine und noch eine.

24
00:01:17,150 --> 00:01:19,100
Aber rekursive Funktionen
kann nicht unendlich sein.

25
00:01:19,100 --> 00:01:23,490
Sie müssen irgendwie zu beenden, oder Ihr
Programm wird ewig laufen.

26
00:01:23,490 --> 00:01:27,680
>> Also müssen wir einen Weg finden, zu brechen
aus den rekursiven Aufrufen.

27
00:01:27,680 --> 00:01:29,900
Wir nennen dies die Basisfall.

28
00:01:29,900 --> 00:01:33,570
Wenn die Basisfall-Bedingung erfüllt,
die Funktion gibt, ohne dass

29
00:01:33,570 --> 00:01:34,950
ein weiterer rekursiven Aufruf.

30
00:01:34,950 --> 00:01:39,610
Nutzen Sie diese Funktion, hallo, eine Leere Funktion
das dauert ein int n als Eingabe.

31
00:01:39,610 --> 00:01:41,260
Der Basisfall kommt zuerst.

32
00:01:41,260 --> 00:01:46,220
Wenn n kleiner als Null ist, und Druck bye
zurück Für alle anderen Fälle, die

33
00:01:46,220 --> 00:01:49,400
Funktion druckt hallo und führen
der rekursive Aufruf.

34
00:01:49,400 --> 00:01:53,600
Ein weiterer Aufruf der Funktion hallo mit
ein Eingangswert verringert.

35
00:01:53,600 --> 00:01:56,790
>> Nun, obwohl wir drucken hallo, das
Funktion wird nicht beendet, bis wir

36
00:01:56,790 --> 00:02:00,370
Rückkehr der Rückgabetyp,
in diesem Fall nichtig.

37
00:02:00,370 --> 00:02:04,830
Also für alle n anderen als der Basisfall
diese Funktion wird wieder hallo hallo

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

39
00:02:06,890 --> 00:02:10,050
Da diese Funktion aber leer, wir
wird nicht explizit Rückkehr geben hier.

40
00:02:10,050 --> 00:02:12,000
Wir müssen nur die Funktion ausführen.

41
00:02:12,000 --> 00:02:16,960
So ruft hallo (3) gedruckt und hallo
hallo ausführen (2), hallo (1) führt ein

42
00:02:16,960 --> 00:02:20,560
welche hallo ausführt (0), wobei die
Base-Case-Bedingung erfüllt ist.

43
00:02:20,560 --> 00:02:24,100
Also hallo (0) druckt Abschied und kehrt zurück.

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

45
00:02:24,990 --> 00:02:28,690
So, jetzt haben wir die Grundlagen der
rekursive Funktionen, die sie benötigen,

46
00:02:28,690 --> 00:02:32,730
mindestens einen Basisfall sowie
rekursiven Aufruf, machen wir weiter, um eine

47
00:02:32,730 --> 00:02:34,120
sinn Beispiel.

48
00:02:34,120 --> 00:02:37,830
Eines, das nicht nur zurückgibt
nichtig, egal was.

49
00:02:37,830 --> 00:02:41,340
>> Werfen wir einen Blick auf die faktorielle
Betrieb am häufigsten verwendet

50
00:02:41,340 --> 00:02:43,660
Wahrscheinlichkeitsberechnungen.

51
00:02:43,660 --> 00:02:48,120
Die Fakultät von n ist das Produkt von jeder
positive ganze Zahl kleiner als

52
00:02:48,120 --> 00:02:49,400
und gleich n ist.

53
00:02:49,400 --> 00:02:56,731
So Fakultät fünf ist 5 mal 4 mal
3 mal 2 mal 1 bis 120 zu geben.

54
00:02:56,731 --> 00:03:01,400
Vier Fakultät ist 4 mal 3 mal
2 mal 1 bis 24 geben.

55
00:03:01,400 --> 00:03:04,910
Und das gleiche gilt
um jede positive ganze Zahl ist.

56
00:03:04,910 --> 00:03:08,670
>> Also, wie könnten wir einen rekursiven
Funktion, die die Fakultät berechnet

57
00:03:08,670 --> 00:03:09,960
einer Anzahl?

58
00:03:09,960 --> 00:03:14,700
Nun, wir müssen zu identifizieren sowohl die
Basisfall und der rekursive Aufruf.

59
00:03:14,700 --> 00:03:18,250
Der rekursive Aufruf wird die gleiche sein
in allen Fällen mit Ausnahme der Basis

60
00:03:18,250 --> 00:03:21,420
Fall, was bedeutet, dass wir uns zu haben,
ein Muster zu finden, die uns unsere

61
00:03:21,420 --> 00:03:23,350
gewünschte Ergebnis.

62
00:03:23,350 --> 00:03:30,270
>> In diesem Beispiel sehen Sie, wie 5 faktorielle
Multiplikation beinhaltet 4 zu 3 nach 2 von 1

63
00:03:30,270 --> 00:03:33,010
Und noch am selben Multiplikation
Hier befindet sich die

64
00:03:33,010 --> 00:03:35,430
Definition von 4 Fakultät.

65
00:03:35,430 --> 00:03:39,810
So sehen wir, dass 5 Fakultät ist
nur 5 x 4 faktorielle.

66
00:03:39,810 --> 00:03:43,360
Jetzt hat dieses Muster anwenden
4 factorial als auch?

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

68
00:03:44,280 --> 00:03:49,120
Wir sehen, dass 4 enthält die faktorielle
Multiplikation 3 mal 2 mal 1, die

69
00:03:49,120 --> 00:03:51,590
sehr gleiche Definition wie 3 Fakultät.

70
00:03:51,590 --> 00:03:56,950
SO 4 faktoriellen gleich 4 mal 3
faktorielle, und so weiter und so fort unserer

71
00:03:56,950 --> 00:04:02,170
Muster-Sticks bis zum 1. Fakultät, die
per Definition gleich 1 ist.

72
00:04:02,170 --> 00:04:04,950
>> Es gibt keine andere positive
Zahlen verlassen.

73
00:04:04,950 --> 00:04:07,870
So haben wir das Muster für
unsere rekursiven Aufruf.

74
00:04:07,870 --> 00:04:13,260
n Fakultät ist gleich dem n-fachen
die Fakultät von n minus 1.

75
00:04:13,260 --> 00:04:14,370
Und unsere Basisfall?

76
00:04:14,370 --> 00:04:17,370
Das wird nur unsere Definition sein
von 1 Fakultät.

77
00:04:17,370 --> 00:04:19,995
>> So, jetzt können wir mit dem Schreiben zu bewegen auf
Code für die Funktion.

78
00:04:19,995 --> 00:04:24,110
Für den Basisfall, müssen wir die
Zustand n = 1 entspricht, wo

79
00:04:24,110 --> 00:04:25,780
wir 1 zurück.

80
00:04:25,780 --> 00:04:29,280
Dann Bewegen auf dem rekursiven Aufruf,
wir n-mal die Rückkehr

81
00:04:29,280 --> 00:04:32,180
Fakultät von n minus 1.

82
00:04:32,180 --> 00:04:33,590
>> Nun wollen wir testen, diese unsere.

83
00:04:33,590 --> 00:04:35,900
Lassen Sie uns versuchen Fakultät 4.

84
00:04:35,900 --> 00:04:39,420
Per unserer Funktion es ist gleich
4 mal faktorielle (3).

85
00:04:39,420 --> 00:04:43,040
Fakultät (3) gleich ist
3 mal faktoriellen (2).

86
00:04:43,040 --> 00:04:48,700
Faktoriellen (2) gleich 2-mal ist
faktorielle (1), die 1 zurück.

87
00:04:48,700 --> 00:04:52,490
Fakultät (2) gibt nun 2 mal 1, 2.

88
00:04:52,490 --> 00:04:55,960
Fakultät (3) kann nun zurückkehren
3 mal 2, 6.

89
00:04:55,960 --> 00:05:02,490
Und schließlich, faktorielle (4)
gibt 4 mal 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Wenn Sie stoßen Schwierigkeiten sind
mit dem rekursiven Aufruf, so tun, als

91
00:05:06,780 --> 00:05:09,660
arbeitet die Funktion bereits.

92
00:05:09,660 --> 00:05:13,450
Was ich damit meine ist, dass Sie sollten
Vertrauen Sie Ihrem rekursive Aufrufe zur Rückkehr

93
00:05:13,450 --> 00:05:15,100
die richtigen Werte.

94
00:05:15,100 --> 00:05:18,960
Zum Beispiel, wenn ich weiß, dass
faktorielle (5) gleich 5 mal

95
00:05:18,960 --> 00:05:24,870
faktorielle (4), werde ich darauf vertrauen, dass
faktorielle (4) wird mir 24.

96
00:05:24,870 --> 00:05:28,510
Betrachten Sie es als eine Variable, wenn Sie
wird, wie wenn Sie bereits definiert

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

98
00:05:30,070 --> 00:05:33,850
So dass für jede faktorielle (n), ist es
das Produkt von n und

99
00:05:33,850 --> 00:05:35,360
die bisherige Fakultät.

100
00:05:35,360 --> 00:05:38,130
Und das vorherige Fakultät
wird durch den Aufruf erhalten

101
00:05:38,130 --> 00:05:41,330
Fakultät von n minus 1.

102
00:05:41,330 --> 00:05:45,130
>> Nun, sehen, wenn Sie implementieren können, ein
rekursive Funktion sich.

103
00:05:45,130 --> 00:05:50,490
Laden Sie Ihre Terminal oder run.cs50.net,
und schreiben Sie eine Funktion Summe

104
00:05:50,490 --> 00:05:54,770
das dauert eine ganze Zahl n und gibt die
Summe aller aufeinander folgende positive

105
00:05:54,770 --> 00:05:57,490
n ganze Zahlen von 1.

106
00:05:57,490 --> 00:06:01,000
Ich habe aus der Summen von einigen geschrieben
Werte, Ihnen zu helfen unsere.

107
00:06:01,000 --> 00:06:04,030
Erstens, herauszufinden, die
Base-Case-Zustand.

108
00:06:04,030 --> 00:06:06,170
Dann schauen Summe (5).

109
00:06:06,170 --> 00:06:09,270
Können Sie es in Bezug auf Ausdruck
einer anderen Summe?

110
00:06:09,270 --> 00:06:11,290
Nun, was Summe (4)?

111
00:06:11,290 --> 00:06:15,630
Wie kann man ausdrücken Summe (4)
in Bezug auf eine andere Summe?

112
00:06:15,630 --> 00:06:19,655
>> Sobald Sie Summe haben (5) und Summe (4)
in Bezug auf andere Summen ausgedrückt finden

113
00:06:19,655 --> 00:06:22,970
Wenn Sie identifizieren können, ein
Muster für die Summe (n).

114
00:06:22,970 --> 00:06:26,190
Wenn nicht, versuchen ein paar andere Zahlen
und drücken ihre Summen in

115
00:06:26,190 --> 00:06:28,410
Bezug auf weitere Zahlen.

116
00:06:28,410 --> 00:06:31,930
Durch die Identifizierung von Mustern für diskrete
Zahlen, auf Ihrem Weg zu du bist gut

117
00:06:31,930 --> 00:06:34,320
Identifizierung des Musters für jedes n.

118
00:06:34,320 --> 00:06:38,040
>> Rekursion ist ein wirklich mächtiges Werkzeug,
so natürlich ist es nicht darauf beschränkt

119
00:06:38,040 --> 00:06:39,820
mathematische Funktionen.

120
00:06:39,820 --> 00:06:44,040
Rekursion kann sehr effektiv eingesetzt werden
beim Umgang mit Bäumen zum Beispiel.

121
00:06:44,040 --> 00:06:47,210
Schauen Sie sich die kurz auf Bäume für ein
gründlichere Überprüfung, aber für jetzt

122
00:06:47,210 --> 00:06:51,140
Daran erinnern, dass binäre Suchbäume, in
Insbesondere werden aus Knoten, die jeweils

123
00:06:51,140 --> 00:06:53,820
mit einem Wert und zwei Knoten Zeiger.

124
00:06:53,820 --> 00:06:57,270
Gewöhnlich wird dies durch die dargestellten
Elternknoten mit einer Zeile Zeige

125
00:06:57,270 --> 00:07:01,870
auf der linken Kindknoten und eines
auf der rechten untergeordneten Knoten.

126
00:07:01,870 --> 00:07:04,510
Der Aufbau eines binären Such
Baum eignet sich gut

127
00:07:04,510 --> 00:07:05,940
auf eine rekursive Suche.

128
00:07:05,940 --> 00:07:09,730
Die rekursiven Aufruf entweder in den Pässen
linken oder rechten Knoten, aber

129
00:07:09,730 --> 00:07:10,950
der, dass in der Baum kurz.

130
00:07:10,950 --> 00:07:15,690
>> Angenommen, Sie möchten eine Operation ausgeführt werden soll
jeder einzelne Knoten in einem binären Baum.

131
00:07:15,690 --> 00:07:17,410
Wie können Sie über das gehen?

132
00:07:17,410 --> 00:07:20,600
Nun, Sie könnten eine rekursive schreiben
Funktion, die den Vorgang ausführt

133
00:07:20,600 --> 00:07:24,450
auf den übergeordneten Knoten und macht eine rekursive
anrufen, um die gleiche Funktion,

134
00:07:24,450 --> 00:07:27,630
vorbei in den linken und
rechte Kind-Knoten.

135
00:07:27,630 --> 00:07:31,650
Zum Beispiel wird diese Funktion foo, dass
ändert den Wert eines bestimmten Knotens und

136
00:07:31,650 --> 00:07:33,830
alle seine Kinder ein.

137
00:07:33,830 --> 00:07:37,400
Der Basisfall von einem Null-Knoten Ursachen
die Funktion, um zurückzukehren, was

138
00:07:37,400 --> 00:07:41,290
dass es keine Knoten
in diesem Unterbaum links.

139
00:07:41,290 --> 00:07:42,620
>> Lassen Sie uns durch sie hindurchgehen.

140
00:07:42,620 --> 00:07:44,340
Die erste Mutter 13 ist.

141
00:07:44,340 --> 00:07:47,930
Wir ändern den Wert auf 1, und rufen Sie dann
unsere Funktion auf der linken als auch

142
00:07:47,930 --> 00:07:49,600
nach rechts.

143
00:07:49,600 --> 00:07:53,910
Die Funktion, foo, ist auf der linken Seite namens
Teilbaum ersten, so dass der linke Knoten

144
00:07:53,910 --> 00:07:57,730
wird auf 1 und neu zugewiesen werden, wird foo
auf die Kinder dieses Knotens aufgerufen werden,

145
00:07:57,730 --> 00:08:01,900
zuerst die linke und dann die rechte,
und so weiter und so fort.

146
00:08:01,900 --> 00:08:05,630
Und ihnen sagen, dass die Zweige nicht haben
mehr Kinder, damit der gleiche Prozess

147
00:08:05,630 --> 00:08:09,700
wird für die richtigen Kinder weiterhin
Knoten, bis der ganze Baum sind

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

149
00:08:11,430 --> 00:08:15,390
>> Wie Sie sehen können, können Sie nicht beschränkt werden
um nur ein rekursiven Aufruf.

150
00:08:15,390 --> 00:08:17,930
Ebenso viele, wie die Arbeit zu erledigen.

151
00:08:17,930 --> 00:08:21,200
Was, wenn Sie einen Baum hatte, wo jeder
Knoten hatte drei Kinder,

152
00:08:21,200 --> 00:08:23,100
Linke, mittlere und rechte?

153
00:08:23,100 --> 00:08:24,886
Wie würden Sie foo bearbeiten?

154
00:08:24,886 --> 00:08:25,860
Nun, einfach.

155
00:08:25,860 --> 00:08:30,250
Fügen Sie einfach einen weiteren rekursiven Aufruf und
Pass in die Mitte Knotenzeiger.

156
00:08:30,250 --> 00:08:34,549
>> Rekursion ist sehr mächtig und nicht auf
erwähnen, elegant, aber es kann eine werden

157
00:08:34,549 --> 00:08:38,010
schwieriges Konzept auf den ersten, so sein
Patient und nehmen Sie sich Zeit.

158
00:08:38,010 --> 00:08:39,370
Beginnen Sie mit dem Basisfall.

159
00:08:39,370 --> 00:08:42,650
Es ist in der Regel am einfachsten zu identifizieren,
und dann können Sie arbeiten

160
00:08:42,650 --> 00:08:43,830
von dort nach hinten.

161
00:08:43,830 --> 00:08:46,190
Sie wissen, Sie zu erreichen, müssen Sie Ihre
Basisfall, so dass Macht

162
00:08:46,190 --> 00:08:47,760
Ihnen ein paar Hinweise.

163
00:08:47,760 --> 00:08:53,120
Versuchen Sie, ein Sonderfall in Ausdruck
hinsichtlich anderen Fällen oder in Teilmengen.

164
00:08:53,120 --> 00:08:54,700
>> Vielen Dank für diesen kurzen beobachten.

165
00:08:54,700 --> 00:08:58,920
Zumindest, jetzt können Sie
Witze verstehen, wie diese.

166
00:08:58,920 --> 00:09:01,250
Mein Name ist Zamyla, und dies ist CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Nutzen Sie diese Funktion, hallo, ein
Leere Funktion, nimmt

169
00:09:07,170 --> 00:09:09,212
ein int, n, als Eingabe.

170
00:09:09,212 --> 00:09:11,020
Der Basisfall kommt zuerst.

171
00:09:11,020 --> 00:09:14,240
Wenn n kleiner als 0 ist, Druck
"Auf Wiedersehen" und zurück.

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