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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: För att förstå
rekursion, måste du

3
00:00:10,190 --> 00:00:13,820
först förstå rekursion.

4
00:00:13,820 --> 00:00:17,280
Att ha rekursion i programkonstruktionsmedel
att du har självrefererande

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

6
00:00:18,570 --> 00:00:21,520
Rekursiva datastrukturer, till exempel,
är datastrukturer som

7
00:00:21,520 --> 00:00:23,990
inkludera sig själva i
deras definitioner.

8
00:00:23,990 --> 00:00:27,160
Men i dag, kommer vi att fokusera
på rekursiva funktioner.

9
00:00:27,160 --> 00:00:31,160
>> Minns att funktioner tar ingångar,
argument, och returnera ett värde som deras

10
00:00:31,160 --> 00:00:34,480
utgång representeras av
detta diagram här.

11
00:00:34,480 --> 00:00:38,060
Vi ska tänka på lådan som kroppen av
den funktion, som innehåller uppsättningen av

12
00:00:38,060 --> 00:00:42,340
instruktioner som tolkar
indata och åstadkomma en utsignal.

13
00:00:42,340 --> 00:00:45,660
Ta en närmare titt inuti kroppen av
funktionen kan avslöja samtal till

14
00:00:45,660 --> 00:00:47,430
andra funktioner också.

15
00:00:47,430 --> 00:00:51,300
Ta denna enkla funktion, foo, att
tar en sträng som indata och

16
00:00:51,300 --> 00:00:54,630
skriver hur många bokstäver
att strängen har.

17
00:00:54,630 --> 00:00:58,490
Funktionen strlen, för stränglängd,
heter, vars utgång är

18
00:00:58,490 --> 00:01:01,890
krävs för samtalet till printf.

19
00:01:01,890 --> 00:01:05,770
>> Nu, vad som gör en rekursiv funktion
speciell är att den kallar sig.

20
00:01:05,770 --> 00:01:09,610
Vi kan representera denna rekursiva
ringa med denna orange pil

21
00:01:09,610 --> 00:01:11,360
loopa tillbaka till sig själv.

22
00:01:11,360 --> 00:01:15,630
Men köra själv igen kommer bara
gör ett annat rekursivt anrop, och

23
00:01:15,630 --> 00:01:17,150
en annan och en annan.

24
00:01:17,150 --> 00:01:19,100
Men rekursiva funktioner
kan inte vara oändlig.

25
00:01:19,100 --> 00:01:23,490
De måste sluta på något sätt, eller din
Programmet kommer att köra för evigt.

26
00:01:23,490 --> 00:01:27,680
>> Så vi måste hitta ett sätt att bryta
ut ur de rekursiva anrop.

27
00:01:27,680 --> 00:01:29,900
Vi kallar detta basfallet.

28
00:01:29,900 --> 00:01:33,570
När basfallet villkor är uppfyllt,
returnerar funktionen utan att göra

29
00:01:33,570 --> 00:01:34,950
ett rekursivt anrop.

30
00:01:34,950 --> 00:01:39,610
Ta denna funktion, hej, ett tomrum funktion
som tar en int n som indata.

31
00:01:39,610 --> 00:01:41,260
Basen fall kommer först.

32
00:01:41,260 --> 00:01:46,220
Om n är mindre än noll, skriva ut bye och
tillbaka I alla övriga fall, den

33
00:01:46,220 --> 00:01:49,400
Funktionen kommer att skriva hej och exekvera
det rekursiva anropet.

34
00:01:49,400 --> 00:01:53,600
Ett annat anrop till funktionen hej med
en dekrementeras ingångsvärde.

35
00:01:53,600 --> 00:01:56,790
>> Nu, även om vi skriver ut hej, det
Funktionen kommer inte att upphöra förrän vi

36
00:01:56,790 --> 00:02:00,370
tillbaka sin returtyp,
i detta fall tomrum.

37
00:02:00,370 --> 00:02:04,830
Så för varje n annat än grundsystemet,
denna funktion hi kommer att återvända hi

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

39
00:02:06,890 --> 00:02:10,050
Eftersom denna funktion är ogiltig om, vi
inte uttryckligen skriver retur här.

40
00:02:10,050 --> 00:02:12,000
Vi ska bara köra funktionen.

41
00:02:12,000 --> 00:02:16,960
Så ringer hej (3) kommer att skriva hej och
exekvera hi (2) som exekverar hi (1) en

42
00:02:16,960 --> 00:02:20,560
som exekverar hi (0), där den
basfall villkor uppfylls.

43
00:02:20,560 --> 00:02:24,100
Så hej (0) skriver bye och avkastning.

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

45
00:02:24,990 --> 00:02:28,690
Så nu när vi förstår grunderna i
rekursiva funktioner, som de behöver

46
00:02:28,690 --> 00:02:32,730
minst ett basfall samt en
rekursivt anrop, låt oss gå vidare till en

47
00:02:32,730 --> 00:02:34,120
mer meningsfullt exempel.

48
00:02:34,120 --> 00:02:37,830
En som inte bara tillbaka
ogiltig oavsett vad.

49
00:02:37,830 --> 00:02:41,340
>> Låt oss ta en titt på fakulteten
operation som oftast används i

50
00:02:41,340 --> 00:02:43,660
sannolikhetsberäkningar.

51
00:02:43,660 --> 00:02:48,120
Fakulteten av n är produkten av varje
positivt heltal mindre än

52
00:02:48,120 --> 00:02:49,400
och lika med n.

53
00:02:49,400 --> 00:02:56,731
Så faktoriell fem är 5 gånger 4 gånger
3 gånger 2 gånger 1 för att ge 120.

54
00:02:56,731 --> 00:03:01,400
Fyra fakultet är 4 gånger 3 gånger
2 gånger 1 för att ge 24.

55
00:03:01,400 --> 00:03:04,910
Och samma regel gäller
till något positivt heltal.

56
00:03:04,910 --> 00:03:08,670
>> Så hur kan vi skriva ett rekursivt
funktion som beräknar fakulteten

57
00:03:08,670 --> 00:03:09,960
av ett nummer?

58
00:03:09,960 --> 00:03:14,700
Tja, vi måste identifiera både
basfall och rekursiva anrop.

59
00:03:14,700 --> 00:03:18,250
Den rekursiva anrop kommer att vara samma
i samtliga fall med undantag för basen

60
00:03:18,250 --> 00:03:21,420
fall, vilket innebär att vi måste
hitta ett mönster som ger oss vår

61
00:03:21,420 --> 00:03:23,350
önskade resultatet.

62
00:03:23,350 --> 00:03:30,270
>> För detta exempel, se hur 5 faktoriell
innebär att multiplicera 4 med 3 med 2 av 1

63
00:03:30,270 --> 00:03:33,010
Och det mycket samma multiplikation
finns här, det

64
00:03:33,010 --> 00:03:35,430
definitionen av fyra faktoriell.

65
00:03:35,430 --> 00:03:39,810
Så vi ser att 5 fakultet är
bara 5 gånger 4 fakulteten.

66
00:03:39,810 --> 00:03:43,360
Nu går detta mönster gäller
till 4 faktoriell också?

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

68
00:03:44,280 --> 00:03:49,120
Vi ser att 4 fakultet innehåller
multiplikation 3 gånger 2 gånger 1, den

69
00:03:49,120 --> 00:03:51,590
samma definition som 3 faktoriell.

70
00:03:51,590 --> 00:03:56,950
Så 4 fakultet är lika med 4 gånger 3
faktoriell, och så vidare och så vidare vår

71
00:03:56,950 --> 00:04:02,170
mönster sticker fram 1 faktoriell, vilket
per definition är lika med ett.

72
00:04:02,170 --> 00:04:04,950
>> Det finns ingen annan positiv
heltal kvar.

73
00:04:04,950 --> 00:04:07,870
Så vi har mönstret för
vår rekursivt anrop.

74
00:04:07,870 --> 00:04:13,260
n faktoriell är lika med n gånger
fakulteten av n minus 1.

75
00:04:13,260 --> 00:04:14,370
Och vår bas fallet?

76
00:04:14,370 --> 00:04:17,370
Det ska bara vara vår definition
av en faktoriell.

77
00:04:17,370 --> 00:04:19,995
>> Så nu kan vi gå vidare till att skriva
kod för funktionen.

78
00:04:19,995 --> 00:04:24,110
För basfallet, vi har den
tillstånd n är lika jämlikar 1, där

79
00:04:24,110 --> 00:04:25,780
Vi ska återkomma 1.

80
00:04:25,780 --> 00:04:29,280
Sedan flyttar till rekursivt anrop,
Vi ska återkomma n gånger

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

82
00:04:32,180 --> 00:04:33,590
>> Nu ska vi testa denna vår.

83
00:04:33,590 --> 00:04:35,900
Låt oss försöka faktoriell 4.

84
00:04:35,900 --> 00:04:39,420
Per vår funktion är det lika
till 4 gånger faktoriell (3).

85
00:04:39,420 --> 00:04:43,040
Factorial (3) är lika med
Tre gånger faktoriella (2).

86
00:04:43,040 --> 00:04:48,700
Factorial (2) är lika med två gånger
factorial (1), som returnerar 1.

87
00:04:48,700 --> 00:04:52,490
Factorial (2) ger nu två gånger 1, 2.

88
00:04:52,490 --> 00:04:55,960
Factorial (3) kan nu återvända
3 gånger 2, 6.

89
00:04:55,960 --> 00:05:02,490
Och slutligen, factorial (4)
returnerar 4 gånger 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Om du stöter på några svårigheter
med den rekursiva anrop, låtsas att

91
00:05:06,780 --> 00:05:09,660
funktionen fungerar redan.

92
00:05:09,660 --> 00:05:13,450
Vad jag menar med detta är att du ska
lita på din rekursiva anrop för att återvända

93
00:05:13,450 --> 00:05:15,100
de rätta värdena.

94
00:05:15,100 --> 00:05:18,960
Till exempel, om jag vet att
faktoriell (5) är lika med fem gånger

95
00:05:18,960 --> 00:05:24,870
factorial (4), kommer jag att lita på att
factorial (4) kommer att ge mig 24.

96
00:05:24,870 --> 00:05:28,510
Se det som en variabel, om du
kommer, som om du redan har definierat

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

98
00:05:30,070 --> 00:05:33,850
Så för varje fakultet (n), är det
produkten av n och

99
00:05:33,850 --> 00:05:35,360
föregående faktoriell.

100
00:05:35,360 --> 00:05:38,130
Och detta tidigare faktor
erhålles genom att anropa

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

102
00:05:41,330 --> 00:05:45,130
>> Nu, se om du kan genomföra en
rekursiv funktion själv.

103
00:05:45,130 --> 00:05:50,490
Ladda upp din terminal, eller run.cs50.net,
och skriva en funktionssumma

104
00:05:50,490 --> 00:05:54,770
som tar ett heltal n och returnerar
summan av alla på varandra följande positiva

105
00:05:54,770 --> 00:05:57,490
heltal från n till 1.

106
00:05:57,490 --> 00:06:01,000
Jag har skrivit ut de belopp för vissa
värden för att hjälpa dig vår.

107
00:06:01,000 --> 00:06:04,030
Först räkna ut
basfallet skick.

108
00:06:04,030 --> 00:06:06,170
Titta sedan på summan (5).

109
00:06:06,170 --> 00:06:09,270
Kan du uttrycka det i termer
av en annan summa?

110
00:06:09,270 --> 00:06:11,290
Nu, hur är summan (4)?

111
00:06:11,290 --> 00:06:15,630
Hur kan du uttrycka summa (4)
i fråga om en annan summa?

112
00:06:15,630 --> 00:06:19,655
>> När du har summa (5) och summan (4)
uttryckt i termer av andra belopp, se

113
00:06:19,655 --> 00:06:22,970
Om du kan identifiera en
mönster för summan (n).

114
00:06:22,970 --> 00:06:26,190
Om inte, prova några andra nummer
och uttrycka sina summor i

115
00:06:26,190 --> 00:06:28,410
termer av ett annat nummer.

116
00:06:28,410 --> 00:06:31,930
Genom att identifiera mönster för diskreta
siffror, du är på god väg att

117
00:06:31,930 --> 00:06:34,320
identifiera mönstret för varje n.

118
00:06:34,320 --> 00:06:38,040
>> Rekursion är ett riktigt kraftfullt verktyg,
så naturligtvis det är inte begränsat till

119
00:06:38,040 --> 00:06:39,820
matematiska funktioner.

120
00:06:39,820 --> 00:06:44,040
Rekursion kan användas mycket effektivt
vid hanteringen av träd till exempel.

121
00:06:44,040 --> 00:06:47,210
Kolla in den korta på träd för en
mer grundlig översyn, men för nu

122
00:06:47,210 --> 00:06:51,140
minns att binära sökträd, i
Speciellt består av noder, varvid varje

123
00:06:51,140 --> 00:06:53,820
med ett värde och två noder pekare.

124
00:06:53,820 --> 00:06:57,270
Vanligtvis är denna representeras av
förälder nod som har en linje som pekar

125
00:06:57,270 --> 00:07:01,870
till den vänstra underordnade noden och en
till det högra underordnade noden.

126
00:07:01,870 --> 00:07:04,510
Strukturen hos en binär sökning
träd lämpar sig väl

127
00:07:04,510 --> 00:07:05,940
till en rekursiv sökning.

128
00:07:05,940 --> 00:07:09,730
Den rekursiva anrop passerar antingen i
vänster eller höger nod, men mer

129
00:07:09,730 --> 00:07:10,950
av att i träd korta.

130
00:07:10,950 --> 00:07:15,690
>> Säg att du vill utföra en operation på
varje enskild nod i ett binärt träd.

131
00:07:15,690 --> 00:07:17,410
Hur kan du gå om det?

132
00:07:17,410 --> 00:07:20,600
Tja, skulle du kunna skriva en rekursiv
funktion som utför operationen

133
00:07:20,600 --> 00:07:24,450
på den överordnade noden och gör en rekursiv
ring för att samma funktion,

134
00:07:24,450 --> 00:07:27,630
som passerar i den vänstra och
högra underordnade noder.

135
00:07:27,630 --> 00:07:31,650
Till exempel, den här funktionen foo, som
ändrar värdet för en given nod och

136
00:07:31,650 --> 00:07:33,830
alla sina barn till 1.

137
00:07:33,830 --> 00:07:37,400
Basen Vid en null nod orsakar
funktionen för att återgå, vilket indikerar

138
00:07:37,400 --> 00:07:41,290
att det inte finns några noder
kvar i den underträdet.

139
00:07:41,290 --> 00:07:42,620
>> Låt oss gå igenom det.

140
00:07:42,620 --> 00:07:44,340
Den första föräldern är 13.

141
00:07:44,340 --> 00:07:47,930
Vi ändrar värdet till 1, och sedan ringa
vår funktion till vänster samt

142
00:07:47,930 --> 00:07:49,600
som höger.

143
00:07:49,600 --> 00:07:53,910
Funktionen, foo, kallas till vänster
sub-träd först, så den vänstra noden

144
00:07:53,910 --> 00:07:57,730
kommer att omfördelas till 1 och foo kommer
uppmanas att nodens barn,

145
00:07:57,730 --> 00:08:01,900
först vänster och sedan till höger,
och så vidare och så vidare.

146
00:08:01,900 --> 00:08:05,630
Och tala om för dem att de filialer som inte har
något fler barn så samma process

147
00:08:05,630 --> 00:08:09,700
kommer att fortsätta under de rätta barn
tills hela trädets noder är

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

149
00:08:11,430 --> 00:08:15,390
>> Som ni kan se, är du inte begränsad
att bara ett rekursivt anrop.

150
00:08:15,390 --> 00:08:17,930
Lika många som kommer att få jobbet gjort.

151
00:08:17,930 --> 00:08:21,200
Tänk om du hade ett träd där varje
nod hade tre barn,

152
00:08:21,200 --> 00:08:23,100
Vänster, mitten och höger?

153
00:08:23,100 --> 00:08:24,886
Hur skulle du redigera foo?

154
00:08:24,886 --> 00:08:25,860
Jo, enkelt.

155
00:08:25,860 --> 00:08:30,250
Lägg bara till en annan rekursivt anrop och
passera i mitten noden pekaren.

156
00:08:30,250 --> 00:08:34,549
>> Rekursion är mycket kraftfullt och inte till
nämna elegant, men det kan vara en

157
00:08:34,549 --> 00:08:38,010
svårt begrepp i början, så var
patient och ta din tid.

158
00:08:38,010 --> 00:08:39,370
Börja med basfallet.

159
00:08:39,370 --> 00:08:42,650
Det är oftast lättast att identifiera,
och sedan kan du arbeta

160
00:08:42,650 --> 00:08:43,830
baklänges därifrån.

161
00:08:43,830 --> 00:08:46,190
Du vet att du behöver för att nå din
basfall, så det kanske

162
00:08:46,190 --> 00:08:47,760
ge dig några tips.

163
00:08:47,760 --> 00:08:53,120
Försök att uttrycka ett specifikt fall i
fråga om andra fall, eller i delmängder.

164
00:08:53,120 --> 00:08:54,700
>> Tack för att du tittar på den här korta.

165
00:08:54,700 --> 00:08:58,920
Åtminstone nu kan du
förstå skämt som denna.

166
00:08:58,920 --> 00:09:01,250
Mitt namn är Zamyla, och detta är CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Ta denna funktion, hej, en
void funktion som tar

169
00:09:07,170 --> 00:09:09,212
en int, n, som inmatning.

170
00:09:09,212 --> 00:09:11,020
Basen fall kommer först.

171
00:09:11,020 --> 00:09:14,240
Om n är mindre än 0, print
"Bye" och retur.

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