>> [MUSIC SPILLE]
>> DOUG LLOYD: Du tenker sikkert at koden er bare brukt til å utføre en oppgave.
Du skriver det ut.
Det gjør noe.
Det er ganske mye det.
>> Du kompilere den.
Du kjører programmet.
Du er flink til å gå.
>> Men tro det eller ei, hvis innkoding i lang tid,
du faktisk kan komme til å se kode som noe som er vakkert.
Det løser et problem i en meget interessant måte,
eller er det bare noe virkelig pen om hvordan det ser ut.
Du kan være ler på meg, men det er sant.
Og rekursjon er en vei å liksom få denne ideen
av vakker, elegant utseende kode.
Det løser problemer på måter som er interessante, lett å visualisere,
og overraskende kort.
>> Måten rekursjon verk er, en rekursiv funksjon
er definert som en funksjon som kaller seg selv som en del av sin utførelse.
Det kan virke litt rart, og vi får se en liten bit
om hvordan dette fungerer i et øyeblikk.
Men igjen, disse rekursive prosedyrer er
kommer til å være så elegant fordi de kommer
å løse dette problem uten å ha alle disse andre funksjoner
eller disse lange sløyfer.
Du vil se at disse rekursiv prosedyrer skal se så kort.
Og de virkelig kommer til å gjøre koden ser mye vakrere.
>> Jeg skal gi deg et eksempel av dette for å se hvordan
en rekursiv prosedyre kan defineres.
Så hvis du er kjent med dette fra matte klassen for mange år siden,
Det er noe som heter det faktoriell funksjon, som vanligvis
betegnet som et utropstegn, som er definert i løpet av alle positive heltall.
Og måten n fakultetet beregnes
er du multipliserer alle tallene mindre enn
eller lik n together-- alle heltall mindre enn
eller lik n sammen.
>> Så 5 fakultet er 5 ganger 4 ganger 3 ganger 2 ganger 1.
Og fire fakultet er 4 ganger 3 ganger 2 ganger 1 og så videre.
Du får ideen.
>> Som programmerere, gjør vi ikke bruke n, utropstegn.
Så vi vil definere fakultet funksjon som fakta av n.
Og vi vil bruke fakultet til å opprette en rekursiv løsning på et problem.
Og jeg tror du kan finne at det er mye mer visuelt
tiltalende enn den iterative versjon av denne, hvilken
Vi vil også ta en titt på i et øyeblikk.
>> Så her er et par facts-- pun intended--
om factorial-- den faktoriell funksjon.
Fakultetet av en, som jeg sa, er en.
Fakultetet av to er 2 ganger 1.
Fakultetet av tre er tre ganger 2 ganger 1, og så videre.
Vi snakket om 4 og 5 allerede.
>> Men ser på dette, er ikke dette sant?
Er ikke fakultetet av to like 2 ganger fakultetet av en?
Jeg mener, er fakultetet av en 1.
Så hvorfor kan vi ikke bare si det, siden fakultetet av to er 2 ganger 1,
Det er egentlig bare 2 ganger fakultetet av en?
>> Og deretter utvide den ideen, er ikke fakultetet av 3
bare 3 ganger fakultetet for to?
Og fakultetet av 4 er 4 ganger fakultetet av tre, og så videre?
Faktisk fakultetet av en rekke kan bare
uttrykkes hvis vi kind av gjennomføre dette for alltid.
Vi kan slags general fakultetet problem
Som det er n ganger fakultetet av n minus en.
Det er n ganger produktet av alle tallene mindre enn meg.
>> Denne ideen, denne generalisering av problemet,
tillater oss å rekursivt definere fakultet funksjon.
Når du definerer en funksjon rekursivt, det er
to ting som må være en del av det.
Du må ha noe som kalles en basisprosessen, noe som, når man utløser den,
vil stoppe rekursiv prosess.
>> Ellers er en funksjon som kaller itself-- som du kanskje imagine--
kunne fortsette i det uendelige.
Funksjonen kaller funksjonen kaller funksjonskall
funksjonen kaller funksjonen.
Hvis du ikke har en måte å stoppe det, programmet
bli effektivt fast på en uendelig loop.
Det vil krasje slutt, fordi det vil gå tom for minne.
Men det er ikke poenget.
>> Vi må ha noen annen måte å stoppe ting i tillegg til vårt program krasjer,
fordi et program som krasjer er sannsynligvis ikke vakker eller elegant.
Og så vi kaller dette base case.
Dette er en enkel løsning til et problem som stopper
den rekursive prosessen oppstår.
Så det er en del av en rekursiv funksjon.
>> Den andre delen er den tilbakevendende tilfelle.
Og det er her rekursjon faktisk vil finne sted.
Det er her Funksjonen vil kalle seg.
>> Det vil ikke kalle seg selv på nøyaktig på samme måte som det ble kalt.
Det vil være en liten variasjon som gjør problemet er det
prøver å løse en teeny litt mindre.
Men det vanligvis passerer the buck å løse mesteparten av oppløsningen
til en annen samtale ned linjen.
>> Hvilke av disse ser som basistilfellet her?
Hvilken av disse ser ut som den enkleste løsningen på et problem?
Vi har en haug med fakultetene, og vi kunne fortsette
går on-- 6, 7, 8, 9, 10, og så videre.
>> Men en av disse ser ut som en god sak å være basistilfellet.
Det er en veldig enkel løsning.
Vi trenger ikke å gjøre noe spesielt.
>> Fakultetet av en er bare en.
Vi trenger ikke å gjøre noe multiplikasjon i det hele tatt.
Det virker som om vi kommer å prøve og løse dette problemet,
og vi må stoppe Rekursjon et sted,
vi sannsynligvis vil stoppe det når vi kommer til en.
Vi ønsker ikke å stoppe før det.
>> Så hvis vi definerer vår faktoriell funksjon,
her er et skjelett for hvordan vi kan gjøre det.
Vi trenger å koble disse to things-- basistilfellet og den tilbakevendende tilfelle.
Hva er base case?
Hvis n er lik 1, returnere 1-- det er et veldig enkelt problem å løse.
>> Fakultetet av en er en.
Det er ikke 1 ganger noe.
Det er bare en.
Det er et veldig enkelt faktum.
Og slik som kan være vår base case.
Hvis vi får gått en inn i dette funksjon, vil vi bare tilbake en.
>> Hva er rekursive tilfellet sannsynligvis se ut?
For alle andre tall foruten en, hva er oppskriften?
Vel, hvis vi tar fakultetet av n,
det er n ganger fakultetet av n minus en.
>> Hvis vi tar fakultetet av tre, det er 3 ganger fakultetet av 3 minus 1,
eller to.
Og så hvis vi ikke er ser på en, ellers
avkastning n ganger de fakultetet av n minus en.
Det er ganske grei.
>> Og for å få til å ha litt renere og mer elegant kode
vet at hvis vi har én linje sløyfer eller én linje betingede grener,
vi kan bli kvitt alle de klammeparentes rundt dem.
Så vi kan konsolidere dette til dette.
Dette har nøyaktig den samme funksjonalitet som dette.
>> Jeg bare tar bort den krøllete seler, fordi det er bare én linje
innsiden av de betingede grener.
Så disse oppfører seg likt.
Hvis n er lik 1, returnere en.
Ellers returnere n ganger fakultetet av n minus en.
Så vi gjøre problemet mindre.
Hvis n starter som fem, skal vi tilbake 5 ganger fakultetet av fire.
Og vi vil se i et minutt når vi snakker om samtalen stack-- i en annen video
hvor vi snakker om kaller stack-- vi vil lære
om hvorfor akkurat denne prosessen fungerer.
>> Men mens fakultetet av fem sier tilbake 5 ganger fakultetet av fire, og fire
kommer til å si, OK, vel, retur 4 ganger fakultetet av tre.
Og som du kan se, er vi slags nærmer en.
Vi kommer nærmere og nærmere den til basistilfellet.
>> Og når vi treffer base case, alle av de tidligere funksjoner
har svaret de var ute etter.
Fakultetet av to sa retur 2 ganger fakultetet av en.
Vel, fakultetet av 1 returnerer 1.
Så samtalen for fakultet 2 kan returnere 2 ganger 1,
og gi den tilbake til fakultetet for 3, som venter på dette resultatet.
>> Og så kan det regne resultatet, 3 ganger 2 er 6,
og gi det tilbake til fakultetet av fire.
Og igjen, vi har en video på kallstakken
hvor det er vist en litt mer enn hva jeg sier akkurat nå.
Men dette er det.
Dette alene er løsningen på beregne fakultetet til et tall.
>> Det er bare fire linjer med kode.
Det er ganske kult, ikke sant?
Det er litt sexy.
>> Så generelt, men ikke alltid, en rekursiv funksjon
kan erstatte en loop i et non-rekursiv funksjon.
Så her, side ved side, er den iterative versjon av fakultetet funksjonen.
Begge disse beregne akkurat det samme.
>> Begge beregne fakultetet av n.
Versjonen til venstre bruker rekursjon til å gjøre det.
Versjonen til høyre bruker iterasjon for å gjøre det.
>> Og legg merke til, må vi erklære en variabel et heltall produkt.
Og da er vi loop.
Så lenge n er større enn 0, vi holde multiplisere at produktet av n
og minske n inntil vi beregne produktet.
Slik at disse to funksjonene, igjen, gjøre akkurat det samme.
Men de gjør det ikke i nøyaktig samme måte.
>> Nå er det mulig å har mer enn en basis
Ved eller mer enn ett rekursive tilfelle, avhengig
på hva din funksjon prøver å gjøre.
Du er ikke nødvendigvis bare begrenset til en enkelt base sak eller et enkelt rekursivt
case.
Slik at et eksempel på noe med flere base tilfeller
kan være dette-- den Fibonacci tallrekken.
>> Du husker kanskje fra grunnskole dager
at Fibonacci-sekvensen er definert dette-- som det første elementet er 0.
Det andre element er en.
Begge disse er bare per definisjon.
>> Så alle andre element er definert som summen av n minus 1 og n minus 2.
Slik det tredje elementet ville være 0 pluss 1 er en.
Og da det fjerde elementet vil være det andre element, 1,
pluss den tredje element, en.
Og det ville være to.
Og så videre og så videre.
>> Så i dette tilfellet har vi to base tilfeller.
Hvis n er lik 1, retur 0.
Hvis n er lik 2, returnere en.
Ellers returnere Fibonacci av n minus en pluss Fibonacci n minus to.
>> Så det er flere base tilfeller.
Hva om flere rekursive tilfeller?
Vel, det er noe kalt Collatz gjetninger.
Jeg har ikke tenkt å si, du vet hva det er,
fordi det er faktisk vår endelige Problemet for denne video.
Og det er vår oppgave å jobbe med sammen.
>> Så her er hva Collatz formodning er--
det gjelder for alle positive heltall.
Og det spekulerer at det er alltid mulig å få tilbake
1 hvis du følger disse trinnene.
Hvis n er 1, stopp.
Vi har fått tilbake til 1 hvis n er en.
>> Ellers går gjennom denne prosessen igjen på n dividert med to.
Og se om du kan komme tilbake til en.
Ellers, hvis n er et oddetall, gå gjennom denne prosessen igjen på 3n pluss 1,
eller 3 ganger n pluss 1.
Så her har vi en enkelt base case.
Hvis n er lik 1, stopp.
Vi gjør ikke noe mer rekursjon.
>> Men vi har to rekursive tilfeller.
Hvis n er enda, gjør vi en rekursiv tilfelle, ringer n delt på to.
Hvis n er et oddetall, gjør vi en annen rekursiv saken på 3 ganger n pluss en.
>> Og så målet for denne videoen er å ta en andre, sette videoen
og prøve og skrive dette rekursiv funksjon Collatz
hvor du passerer i en verdi n, og det beregner hvor mange skritt det
tar å komme til en hvis du starter fra n og du følger disse trinnene opp ovenfor.
Hvis n er 1, tar det 0 trinn.
Ellers kommer det til å ta ett skritt pluss imidlertid
mange skritt det tar på hver n dividert med 2 når n er et partall eller 3n pluss 1
hvis n er et oddetall.
>> Nå har jeg satt opp på skjermen her et par test ting for deg,
et par tester saker for deg, for å se hva disse ulike Collatz tallene er,
og også en illustrasjon av trinnene som
trenger å bli gått gjennom så du kan liksom se denne prosessen i aksjon.
Slik at hvis n er lik 1, Collatz n er 0.
Du trenger ikke å gjøre noe for å komme tilbake til en.
Du er allerede der.
>> Dersom n er 2, det tar ett skritt for å få til en.
Du starter med to.
Vel, er to ikke lik en.
Så det kommer til å være ett skritt pluss imidlertid mange skritt det
tar på n delt på to.
>> 2 dividert med 2 er en.
Så det tar ett skritt pluss imidlertid mange skritt det tar for en.
En tar null trinn.
>> For tre, som du kan se, er det ganske få skritt involvert.
Du går fra tre.
Og så du går til 10, 5, 16, 8, 4, 2, 1.
Det tar sju trinn for å komme tilbake til en.
Og som du kan se, det er en par andre testtilfeller her
å teste ut programmet.
Så igjen, pause videoen.
Og jeg skal gå hoppe tilbake nå til hva selve prosessen er her,
hva dette formodning er.
>> Se om du kan finne ut hvordan du definerer Collatz av n
slik at det beregner hvor mange skritt som trengs for å få til en.
Så forhåpentligvis har du stoppet videoen og du er ikke bare venter på meg
for å gi deg svaret her.
Men hvis du er, vel, her er svaret uansett.
>> Så her er en mulig definisjon av Collatz funksjonen.
Vår base case-- hvis n er lik 1, returnerer vi 0.
Det tar ikke noen trinn for å komme tilbake til en.
>> Ellers har vi to rekursive cases-- en for partall og en for Odd.
Måten jeg teste for partall er å sjekke om n mod to lik 0.
Dette er i utgangspunktet igjen, stille spørsmålet,
hvis du husker hva mod er-- om jeg dividere n av to er det ingen resten?
Det ville være et partall.
>> Og så hvis n mod 2 er lik 0 er testing er dette et partall.
Hvis så, jeg ønsker å returnere en, fordi det er absolutt
ta ett skritt pluss Collatz av uansett hvor mange er halvparten av meg.
Ellers ønsker jeg å returnere en pluss Collatz av 3 ganger n pluss 1.
Det var den andre rekursive skritt som vi
kunne ta for å beregne Collatz-- antall skritt
det tar å komme tilbake til en gitt et nummer.
Så forhåpentligvis, dette eksempelet ga deg litt
av en smak av rekursive prosedyrer.
Forhåpentligvis, tror du koden er en litt vakrere hvis implementert
i en elegant, rekursiv måte.
Men selv om ikke, er rekursjon en virkelig kraftig verktøy likevel.
Og så det er definitivt noe å få hodet rundt,
fordi du vil være i stand til å skape ganske kule programmer ved hjelp av rekursjon
som ellers kan være komplisert å skrive hvis du bruker loops og gjentakelse.
Jeg er Doug Lloyd.
Dette er CS50.