>> ZAMYLA: For at forstå rekursion, skal du
først forstå rekursion.
Under rekursion i programmets design betyder at du har selvrefererende
definitioner.
Rekursive datastrukturer, for eksempel, er datastrukturer,
omfatte sig i deres definitioner.
Men i dag, vi kommer til at fokusere på rekursive funktioner.
>> Husk på, at funktioner tager input, argumenter, og returnerer en værdi som deres
output repræsenteret ved dette diagram her.
Vi vil tænke på boksen som kroppen af funktion, der indeholder sættet af
instruktioner, der fortolker input og giver et output.
Tage et nærmere kig ind i kroppen af funktionen kan afsløre opkald til
andre funktioner samt.
Tag denne enkle funktion, foo, at tager en enkelt streng som input og
prints, hvor mange breve denne streng har.
Funktionen strlen for streng længde, kaldes, hvis produktion er
kræves for opkaldet til printf.
>> Nu, hvad der gør en rekursiv funktion specielle er, at det kalder sig.
Vi kan repræsentere denne rekursive kalde med denne orange pil
looping tilbage til sig selv.
Men udfører selv igen kun vil foretage endnu en rekursivt kald, og
en anden og en anden.
Men rekursive funktioner kan ikke være uendelig.
De skal ende med en eller anden måde, eller din Programmet vil køre for evigt.
>> Så vi er nødt til at finde en måde at bryde ud af de rekursive kald.
Vi kalder denne base case.
Når basen sagen betingelse er opfyldt, returnerer funktionen uden at foretage
et rekursivt kald.
Tag denne funktion, hej, en void funktion der tager en int n som input.
Basen sag kommer først.
Hvis n er mindre end nul, print farvel og tilbage For alle andre tilfælde
funktion udskrives hi og udføre rekursive kald.
Et andet opkald til funktionen hi med en dekrementeres inputværdi.
>> Nu, selv om vi udskriver hej, det Funktionen vil ikke opsige indtil vi
returnere dens returtype, i dette tilfælde ugyldig.
Så for hver n andet end basisscenariet, denne funktion hi vender hi
n minus 1.
Da denne funktion er ugyldig, selvom vi vil ikke eksplicit skrive tilbagevenden her.
Vi vil bare udføre funktionen.
Så at kalde hi (3) udskrives hi og udføre hi (2), som udfører hi (1) en
som udfører hi (0), hvor base case betingelse er opfyldt.
Så hej (0) udskriver farvel og afkast.
>> OK.
Så nu, at vi forstår det grundlæggende i rekursive funktioner, som de har brug for
mindst en base sag samt en rekursivt kald, lad os gå videre til en
mere meningsfuld eksempel.
En, der ikke bare vender tilbage ugyldig uanset hvad.
>> Lad os tage et kig på fakulteten operation mest almindeligt i
sandsynlighedsberegninger.
Factorial n er produktet af hver positivt heltal mindre end
og lige til n.
Så factorial fem er 5 gange 4 gange 3 gange 2 gange 1 for at give 120.
Fire factorial er 4 gange 3 gange 2 gange 1 for at give 24.
Og det samme gælder til et positivt heltal.
>> Så hvordan kan vi skriver en rekursiv funktion, der beregner fakultet
af et nummer?
Nå, vi bliver nødt til at identificere både base case og rekursive kald.
Den rekursive kald vil være den samme for alle tilfælde med undtagelse af bunden
tilfælde, hvilket betyder, at vi bliver nødt til at finde et mønster, der vil give os vores
ønskede resultat.
>> For dette eksempel, se hvordan 5 factorial består i at gange 4 til 3 med 2 af 1
Og det samme multiplikation findes her, den
definition af 4 faktoriel.
Så vi kan se, at 5 factorial er kun 5 gange 4 fakultet.
Nu gør dette mønster gælder til 4 faktoriel så godt?
Ja.
Vi ser, at 4 factorial indeholder multiplikation 3 gange 2 gange 1, den
meget samme definition som 3 fakultet.
Så 4 fakultet er lig med 4 gange 3 faktoriel, og så videre og så videre vores
mønster stikker indtil 1. faktoriel, som definition er lig med 1.
>> Der er ingen andre positive heltal venstre.
Så vi har mønsteret for vores rekursivt kald.
n fakultet er lig med n gange fakultet af n minus 1.
Og vores base case?
Det vil bare være vores definition 1 faktoriel.
>> Så nu kan vi gå videre til at skrive kode for funktionen.
For basisscenariet, vil vi have det betingelse n er lig med lig 1, hvor
vi 1 tilbage.
Så flytter ind på det rekursive kald, vi vil vende tilbage n gange den
faktoriel n minus 1.
>> Lad os nu teste dette vores.
Lad os prøve factorial 4.
Per vores funktion det er lig til 4 gange factorial (3).
Factorial (3) er lig med 3 gange faktoreffekter (2).
Factorial (2) er lig med 2 gange fakultet (1), som returnerer 1.
Factorial (2) returnerer nu 2 gange 1, 2.
Factorial (3), kan nu vende tilbage 3 gange 2, 6.
Og endelig, fakultet (4) returnerer 4 gange 6, 24.
>> Hvis du støder på nogen problemer med det rekursive kald, foregive, at
funktionen fungerer allerede.
Hvad jeg mener med dette er, at du skal tillid til dine rekursive kald til at vende tilbage
de rette værdier.
For eksempel, hvis jeg ved, at factorial (5) er lig med 5 gange
fakultet (4), vil jeg tillid til, at fakultet (4) vil give mig 24.
Tænk på det som en variabel, hvis du vil, som hvis du allerede defineret
fakultet (4).
Så for enhver fakultet (n), er det produktet af n og
forrige faktorforsøg.
Og denne tidligere factorial opnås ved at kalde
faktoriel n minus 1.
>> Nu, se om du kan gennemføre en rekursiv funktion selv.
Indlæse din terminal, eller run.cs50.net, og skrive en sumfunktion
der tager et heltal n og returnerer summen af ​​alle på hinanden følgende positive
heltal fra N til 1.
Jeg har skrevet ud summerne af nogle værdier til at hjælpe dig vores.
Først finde ud af det base case tilstand.
Så se på sum (5).
Kan du udtrykke det i form anden sum?
Nu, hvad sum (4)?
Hvordan kan du udtrykke sum (4) i form af en anden sum?
>> Når du har sum (5) og sum (4) udtrykt i andre beløb, se
hvis du kan identificere en mønster for sum (n).
Hvis ikke, så prøv et par andre numre og udtrykke deres beløb i
form af et andet tal.
Ved at identificere mønstre for diskrete numre, er du godt på vej til
identificere mønsteret for enhver n.
>> Rekursion er en virkelig kraftfuldt værktøj, så det er selvfølgelig ikke begrænset til
matematiske funktioner.
Rekursion kan bruges meget effektivt når der beskæftiger sig med træer for eksempel.
Tjek kort på træerne for en mere grundig gennemgang, men for nu
erindre om, at binære søgetræer, i især består af knuder, der hver
med en værdi og to node pointere.
Normalt er denne repræsenteret ved forælder node har en linie peger
til venstre barneknudepunkt og en til højre barneknudepunkt.
Strukturen af ​​en binær søgning træ egner sig godt
en rekursiv søgning.
Den rekursivt kald passerer enten i højre eller venstre knudepunkt, men mere
af, at træet kort.
>> Sig du ønsker at udføre en operation på hver enkelt node i et binært træ.
Hvordan kan du gå om det?
Nå, kan du skrive en rekursiv funktion, der udfører operationen
på den overordnede node og gør en rekursiv ringe til den samme funktion,
passerer i venstre rigtige barn noder.
For eksempel denne funktion foo, at ændrer værdien af ​​en bestemt node og
alle sine børn til 1..
Basen tilfælde af en Null-node årsager funktionen til at vende tilbage, hvilket indikerer,
at der ikke er nogen knuder til venstre i denne sub-tree.
>> Lad os gå igennem det.
Den første forælder er 13..
Vi ændre værdien til 1, og derefter kalde vores funktion til venstre så godt
som højre.
Den funktion, foo, kaldes til venstre sub-tree først, så det venstre knudepunkt
vil blive overført til 1 og foo vil blive kaldt på nodens børn
først venstre og derefter højre, og så videre og så videre.
Og fortælle dem, at filialer ikke har nogen flere børn, så den samme proces
vil fortsætte i de rigtige børn indtil hele træets knudepunkter er
omfordelt til 1..
>> Som du kan se, er du ikke begrænset til blot én rekursivt kald.
Lige så mange, som vil få arbejdet gjort.
Hvad hvis du havde et træ, hvor hver node havde tre børn,
Venstre, midterste og højre?
Hvordan ville du redigere foo?
Nå, enkel.
Blot tilføje en anden rekursivt kald og passerer i midten node pointer.
>> Rekursion er meget stærk og ikke nævne elegant, men det kan være en
vanskeligt begreb i første omgang, så vær patient og tage din tid.
Start med basisscenariet.
Det er normalt den nemmeste at identificere, og derefter kan du arbejde
baglæns derfra.
Du ved, du har brug for at nå dine base case, så måske
give dig et par hints.
Prøv at udtrykke en konkret sag i form af andre sager, eller i sub-sæt.
>> Tak for at se denne korte.
I det mindste, nu kan du forstå vittigheder som denne.
Mit navn er Zamyla, og det er CS50.
>> Tag denne funktion, hej, et void funktion, der tager
en int, n, som input.
Basen sag kommer først.
Hvis n er mindre end 0, print "Farvel", og tilbagevenden.