>> ZAMYLA: For å forstå rekursjon, må du
først forstå rekursjon.
Å ha rekursjon i programmet design midler at du har selv-referensiell
definisjoner.
Rekursive datastrukturer, for eksempel, er datastrukturer som
inkludere seg selv i sine definisjoner.
Men i dag, kommer vi til å fokusere på rekursive funksjoner.
>> Husker at funksjoner ta innganger, argumenter, og returnerer en verdi som deres
utgang representert ved dette diagrammet her.
Vi vil tenke på boksen som kroppen av funksjon, som inneholder et sett av
instruksjoner som tolker den inngangen og gir et utgangssignal.
Å ta en nærmere titt på innsiden av kroppen av funksjonen kunne avsløre samtaler til
andre funksjoner i tillegg.
Ta denne enkle funksjonen, foo, at tar en enkelt streng som input og
utskrifter hvor mange bokstaver at strengen har.
Funksjonen strlen, for streng lengde, heter, hvis utgang er
nødvendig for kallet til printf.
>> Nå, hva som gjør en rekursiv funksjon spesielle er at det kaller seg.
Vi kan representere denne rekursive ringe med denne oransje pil
sløyfe tilbake til seg selv.
Men gjennomføring seg igjen bare vil foreta en ny rekursive kall, og
en annen, og en annen.
Men rekursive funksjoner kan ikke være uendelig.
De har å ende en eller annen måte, eller din programmet vil kjøre for alltid.
>> Så vi må finne en måte å bryte ut av den rekursive anrop.
Vi kaller dette base case.
Når basen tilfelle betingelsen er oppfylt, returnerer funksjonen uten å gjøre
annen rekursive kall.
Ta denne funksjonen, hi, et tomrom funksjon som tar en int n som input.
Basen saken kommer først.
Hvis n er mindre enn null, print bye og returnere For alle andre tilfeller,
Funksjonen vil skrive hei og utføre den rekursive kall.
Et annet kall til funksjonen hi med en dekrementert inngangsverdi.
>> Nå, selv om vi skriver ut hi, den Funksjonen vil ikke opphøre før vi
returnere sin returtype, i dette tilfellet ugyldig.
Slik at for hver n annen enn basis tilfellet denne funksjonen hi vil returnere hi
n minus en.
Siden denne funksjonen er ugyldig skjønt, vi vil ikke eksplisitt skriver retur her.
Vi skal bare utføre funksjonen.
Så ringer hi (3) vil skrive ut hi og utføre hi (2) som utfører hi (1) en
som kjører hi (0), hvor base case betingelse er oppfylt.
Så hi (0) skriver bye og avkastning.
>> OK.
Så nå som vi forstår det grunnleggende rekursive funksjoner, som de trenger
i det minste en basis tilfelle, så vel som en rekursive kall, la oss gå videre til en
mer meningsfylt eksempel.
En som ikke bare returnere ugyldig uansett hva.
>> La oss ta en titt på fakultetet drift brukes oftest i
sannsynlighetsregning.
Factorial av n er produktet av hvert positive heltall mindre enn
og lik n..
Så faktoriell fem er fem ganger fire ganger 3 ganger 2 ganger 1 for å gi 120.
Fire fakultet er fire ganger tre ganger 2 ganger en å gi 24.
Og den samme regelen gjelder til noe positivt heltall.
>> Så hvordan kan vi skrive en rekursiv funksjon som beregner fakultet
av et tall?
Vel, vi trenger å identifisere både base case og rekursive kall.
Den rekursive kall vil være den samme i alle tilfeller bortsett fra base
saken, noe som betyr at vi må finne et mønster som vil gi oss vår
ønskede resultat.
>> For dette eksempelet, se hvordan fem fakultet innebærer multiplisere fire av tre med to av en
Og det samme multiplikasjon er funnet her,
definisjon av fire fakultet.
Så vi ser at fem fakultet er bare fem ganger fire fakultet.
Nå gjelder dette mønsteret til 4 faktoriell også?
Ja.
Vi ser at fire fakultet inneholder multiplikasjon 3 ganger 2 ganger 1, den
samme definisjon som tre fakultet.
Så fire fakultet er lik fire ganger tre fakultetet, og så videre og så videre vår
mønster stikker frem en fakultet, som ved definisjon er lik 1.
>> Det er ingen annen positiv heltall igjen.
Så vi har et mønster for vår rekursive kall.
n fakultet er lik n ganger fakultetet av n minus en.
Og vår base case?
Det vil bare være vår definisjon av en fakultet.
>> Så nå kan vi gå videre til å skrive kode for funksjonen.
For base case, vil vi ha betingelse n er lik 1, hvor likeverdige
vi vil komme tilbake en.
Deretter går videre til den rekursive kall, vi vil komme tilbake n ganger
fakultetet av n minus en.
>> Nå la oss teste denne vår.
La oss prøve faktoriell 4.
Per vår funksjon det er lik til 4 ganger faktoriell (3).
Fakultet (3) er lik 3 ganger faktorielle (2).
Factorial (2) er lik to ganger fakultet (1), som returnerer en.
Fakultet (2) returnerer nå 2 ganger 1, 2.
Fakultet (3) kan nå gå tilbake 3 ganger 2, 6.
Og til slutt, fakultet (4) returnerer 4 ganger 6, 24.
>> Hvis du støter på noen problemer med den rekursive kall, late som
funksjonen fungerer allerede.
Hva jeg mener med dette er at du bør stole på dine rekursive kall til å vende tilbake
de rette verdiene.
For eksempel, hvis jeg vet at fakultet (5) er lik fem ganger
fakultet (4), kommer jeg til å stole på at fakultet (4) vil gi meg 24.
Tenk på det som en variabel, hvis du vil, som om du allerede har definert
fakultet (4).
Så for alle fakultet (n), er det produktet av n og
forrige fakultet.
Og dette forrige fakultet oppnås ved å ringe
fakultetet av n minus en.
>> Nå, se om du kan gjennomføre en rekursiv fungere selv.
Laste opp din terminal, eller run.cs50.net, og skrive en funksjon sum
som tar et helt tall n og returnerer Summen av alt sammenhengende positiv
heltall fra n til 1.
Jeg har skrevet ut summene av noen verdier for å hjelpe deg vår.
Først finne ut av base case tilstand.
Så, se på summen (5).
Kan du uttrykke det i form av en annen sum?
Nå, hva om sum (4)?
Hvordan kan du uttrykke sum (4) i forhold til en annen sum?
>> Når du har sum (5) og sum (4) uttrykkes i form av andre summer, se
hvis du kan identifisere en mønster for summen (n).
Hvis ikke, kan du prøve noen andre tall og uttrykke sine summer i
forhold til en annen tall.
Ved å identifisere mønstre for diskret tall, er du godt på vei til å
identifisere mønsteret for alle n.
>> Rekursjon er en veldig kraftig verktøy, så selvfølgelig det ikke er begrenset til
matematiske funksjoner.
Rekursjon kan brukes svært effektivt når du arbeider med trær for eksempel.
Sjekk ut kort på trær for en mer grundig gjennomgang, men for nå
Husker at binære søketrær, i Spesielt er bygget opp av knutepunkter som hver
med en verdi og to nodepekere.
Vanligvis er dette representert ved forelder node ha en linje som peker
til venstre for barnenode og en til høyre barnenode.
Strukturen av et binært søk tre egner seg godt
til en rekursiv søk.
Den rekursive kall enten går i venstre eller høyre node, men mer
av det i treet kort.
>> Si at du ønsker å utføre en operasjon på hver eneste node i et binært tre.
Hvordan kan du gå om det?
Vel, kan du skrive en rekursiv funksjon som utfører operasjonen
på foreldrenoden og gjør en rekursiv ring til den samme funksjon,
passering i den venstre og høyre barn noder.
For eksempel denne funksjonen, foo, at endrer verdien av en gitt node og
alle sine barn til en.
Basen tilfelle av en nullnode årsaker funksjonen for å gå tilbake, noe som indikerer
at det ikke er noen noder igjen i det sub-treet.
>> La oss gå gjennom den.
Den første av foreldrene er 13.
Vi endrer verdien til 1, og deretter ringe vår funksjon på venstre så vel
som den riktige.
Funksjonen, foo, kalles på venstre sub-treet først, slik at den venstre noden
vil bli overført til en og foo vil kalles på at node barn,
første til venstre og deretter til høyre, og så videre og så videre.
Og fortell dem at grenene ikke har noen flere barn slik at den samme prosessen
vil fortsette for de riktige barn inntil hele treets noder er
omplassert til en.
>> Som du kan se, er du ikke begrenset til bare én rekursive kall.
Like mange som vil få jobben gjort.
Hva hvis du hadde et tre der hver node hadde tre barn,
Venstre, midtre og høyre?
Hvordan ville du redigere foo?
Vel, enkelt.
Bare å legge til rekursive kall og passere i midten nodepekeren.
>> Rekursjon er veldig kraftig, og ikke til nevne elegant, men det kan være en
vanskelig begrep i begynnelsen, så vær tålmodig og ta deg god tid.
Start med base case.
Det er som regel lettest å identifisere, og da kan du jobbe
bakover derfra.
Du vet at du trenger for å nå dine base case, slik at makt
gi deg noen hint.
Prøv å uttrykke en konkret sak i vilkårene i andre tilfeller, eller i sub-sett.
>> Takk for å se denne korte.
I det minste, nå kan du forstå vitser som dette.
Mitt navn er Zamyla, og dette er CS50.
>> Ta denne funksjonen, hi, en void funksjon som tar
en int, n som inndata.
Basen saken kommer først.
Hvis n er mindre enn 0, print "Bye" og avkastning.