>> [Musik spiller]
>> DOUG LLOYD: Du tror sikkert, at kode bare bruges til at udføre en opgave.
Du skriver det ud.
Det gør noget.
Det er temmelig meget det.
>> Du kompilere det.
Du kører programmet.
Du er god til at gå.
>> Men tro det eller ej, hvis du kode i lang tid,
du faktisk kan komme til at se kode som noget, der er smukt.
Det løser et problem i en meget interessant måde,
eller der er bare noget rigtig pæn om den måde, det ser ud.
Du kan være griner på mig, men det er sandt.
Og rekursion er en måde at slags få denne idé
af smukke, elegante udseende kode.
Det løser problemer på en måde, er interessante, let at visualisere,
og overraskende kort.
>> VEJEN rekursionsudtryk værker er en rekursiv funktion
er defineret som en funktion, der kræver selv som en del af dens fuldbyrdelse.
Det kan virke lidt mærkeligt, og vi vil se en lille smule
om, hvordan det fungerer i et øjeblik.
Men igen, disse rekursive procedurer er
kommer til at være så elegant fordi de kommer
at løse dette problem uden have alle disse andre funktioner
eller disse lange loops.
Du vil se, at disse rekursive procedurer kommer til at se så kort.
Og de virkelig vil gøre din kode ser meget smukkere.
>> Jeg vil give dig et eksempel dette for at se, hvordan
en rekursiv procedure kan defineres.
Så hvis du er fortrolig med dette fra matematik klasse for mange år siden,
der hedder noget faktoriel funktion, der normalt er
betegnet som et udråbstegn, som er defineret i alle positive heltal.
Og den måde, n fakultet beregnes
er du gange alle tallene mindre end
eller lig med n together-- alle heltal mindre end
eller lig med n sammen.
>> Så 5 faktorielt er 5 gange 4 gange 3 gange 2 gange 1.
Og 4 faktorielt er 4 gange 3 gange 2 gange 1 og så videre.
Du får den idé.
>> Som programmører, gør vi ikke bruge n, udråbstegn.
Så vi vil definere fakultet funktion som faktisk af n.
Og vi vil bruge fakultet til at oprette en rekursiv løsning på et problem.
Og jeg tror, ​​du kan finde at det er meget mere visuelt
tiltrækkende end den iterative version af denne, som
Vi vil også tage et kig på et øjeblik.
>> Så her er et par af facts-- ordspil intended--
om factorial-- den faktoriel funktion.
Fakultet af 1, som jeg sagde, er 1.
Fakultet af 2 er 2 gange 1.
Fakultet af 3 er 3 gange 2 gange 1, og så videre.
Vi talte om 4 og 5 allerede.
>> Men ser man på dette, er det ikke sandt?
Er det ikke fakultet af 2 lige 2 gange fakultet af en?
Jeg mener, fakultet af 1 er 1.
Så hvorfor kan vi ikke bare sige, da fakultet af 2 er 2 gange 1,
det er virkelig kun 2 gange fakultet af en?
>> Og derefter at udvide denne idé, er ikke fakultet af 3
kun 3 gange fakultet af 2?
Og fakultet af 4 er 4 gange fakultet af 3 og så videre?
Faktisk fakulteten af et vilkårligt antal kan bare
udtrykkes hvis vi slags af udføre dette for evigt.
Vi kan slags generalisere fakultet problem
da det er n gange fakultet af n minus 1.
Det er n gange produktet af alle tal mindre end mig.
>> Denne idé, dette generalisering af problemet,
tillader os at rekursivt definerer fakultet funktion.
Når du definerer en funktion rekursivt, der er
to ting, der skal være en del af det.
Du skal have noget, der hedder en base case, som, når du udløser det,
vil stoppe den rekursive proces.
>> Ellers en funktion, der kræver itself-- som du måske imagine--
kunne blive ved for evigt.
Funktion kalder funktionen kalder funktionskald
funktionen kalder funktionen.
Hvis du ikke har en måde at stoppe det, dit program
vil effektivt blive hængende ved en uendelig løkke.
Det vil gå ned til sidst, fordi det vil løbe tør for hukommelse.
Men det er ved siden af ​​punktet.
>> Vi er nødt til at have en anden måde at stoppe ting udover vores program bryder sammen,
fordi et program, der går ned er sandsynligvis ikke smuk eller elegant.
Og så kalder vi det basisscenariet.
Dette er en enkel løsning på et problem, som stopper
den rekursive proces opstår.
Så det er en del af en rekursiv funktion.
>> Den anden del er den rekursive tilfældet.
Og det er her, rekursion rent faktisk vil finde sted.
Det er her den funktion vil kalde sig selv.
>> Det vil ikke kalde sig på nøjagtig på samme måde, det blev kaldt.
Det vil være en lille variation der gør det problem, det er
forsøger at løse en teeny smule mindre.
Men det generelt passerer buck løse størstedelen af ​​opløsningen
til et andet opkald ned linjen.
>> Hvilke af disse udseende ligesom basen tilfældet her?
Hvilken en af ​​disse ligner enkleste løsning på et problem?
Vi har en flok af fakulteterne, og vi kunne fortsætte
gå on-- 6, 7, 8, 9, 10 og så videre.
>> Men en af ​​disse ligner en god sag til at være base tilfældet.
Det er en meget simpel løsning.
Vi behøver ikke at gøre noget særligt.
>> Fakultet af 1 er kun 1.
Vi behøver ikke at gøre noget multiplikation overhovedet.
Det ser ud som om vi skal hen at forsøge at løse dette problem,
og vi er nødt til at stoppe Rekursion et eller andet sted,
vi sandsynligvis ønsker at stoppe det, når vi kommer til en.
Vi ønsker ikke at stoppe, før det.
>> Så hvis vi definerer vores faktoriel funktion,
her er et skelet til hvordan vi kan gøre det.
Vi er nødt til at tilslutte de to things-- grundscenariet og rekursive sagen.
Hvad er basisscenariet?
Hvis n er lig med 1, returnere 1-- det er et virkelig simpelt problem at løse.
>> Fakultet af 1 er 1.
Det er ikke 1 gange noget.
Det er kun 1.
Det er en meget nem kendsgerning.
Og så kan være vores base tilfældet.
Hvis vi bliver passeret 1 ind i denne funktion, vil vi bare vende tilbage 1.
>> Hvad er den rekursive tilfælde formentlig se ud?
For hver anden række foruden 1, hvad er mønstret?
Tja, hvis vi tager fakultet af n,
det er n gange fakultet af n minus 1.
>> Hvis vi tager fakultet af 3, det er 3 gange fakultet af 3 minus 1,
eller 2.
Og så hvis vi ikke er ser på 1, ellers
tilbagevenden n gange fakultet af n minus 1.
Det er ret ligetil.
>> Og af hensyn til at have lidt renere og mere elegant kode,
ved, at hvis vi har en enkelt linje loops eller single-line betingede grene,
vi kan slippe af med alle de krøllede parenteser omkring dem.
Så vi kan konsolidere denne til dette.
Dette har nøjagtig samme funktionalitet som dette.
>> Jeg er bare at tage væk krøllede seler, for der er kun én linje
indersiden af ​​disse betingede grene.
Så disse opfører sig ens.
Hvis n er lig med 1, returnere 1.
Ellers returnerer n gange fakultet af n minus 1.
Så vi gøre problemet mindre.
Hvis n starter som 5, vil vi tilbage 5 gange fakultet af 4.
Og vi vil se i et minut, når vi taler om opkaldet stack-- i en anden video
hvor vi taler om kalder stack-- vi vil lære
om, hvorfor netop denne proces fungerer.
>> Men mens fakultet af 5 siger tilbage 5 gange fakultet af 4, og 4
kommer til at sige, OK, godt, afkast 4 gange fakultet af 3.
Og som du kan se, er vi slags nærmer 1.
Vi kommer tættere og tættere på base case.
>> Og når vi ramte bunden tilfældet, alle de tidligere funktioner
har svaret, de ledte efter.
Fakultet af 2 sagde afkast 2 gange fakultet af 1.
Nå, fakultet af 1 giver 1.
Så opfordringen til fakultet 2 kan returnere 2 gange 1,
og give det tilbage til fakultet af 3, som venter på dette resultat.
>> Og så kan det beregne dens resultat, 3 gange 2 er 6,
og give det tilbage til fakultet af 4.
Og igen, vi har en video på opkald stakken
hvor dette er illustreret en lille mere end hvad jeg siger lige nu.
Men det er det.
Dette alene er løsningen på beregning fakultet af et tal.
>> Det er kun fire linjer kode.
Det er ret cool, ikke?
Det er lidt sexet.
>> Så i almindelighed, men ikke altid, en rekursiv funktion
kan erstatte en løkke i en ikke-rekursiv funktion.
Så her, ved siden af ​​hinanden, er den iterative version af fakulteten funktion.
Begge disse beregne nøjagtig det samme.
>> De har begge beregne fakultet af n.
Versionen til venstre bruger rekursion til at gøre det.
Versionen til højre bruger iteration til at gøre det.
>> Og varsel, vi er nødt til at erklære en variabel et heltal produkt.
Og så har vi løkke.
Så længe n er større end 0, vi holde multiplicere resultatet med n
og dekrementere n indtil beregner vi produktet.
Så disse to funktioner, igen, gør præcis det samme.
Men de gør det ikke i nøjagtig samme måde.
>> Nu er det muligt at har mere end én base
tilfælde eller mere end en rekursiv tilfælde afhængigt
om, hvad din funktion er at forsøge at gøre.
Du er ikke nødvendigvis kun begrænset til en enkelt base case eller en enkelt rekursiv
tilfælde.
Så et eksempel på noget med flere baser sager
kunne være denne-- den Fibonacci-talrækken.
>> Du husker måske fra elementære skoledage
at Fibonacci sekvensen er defineret ligesom denne-- det første element er 0.
Det andet element er 1.
Begge disse er blot ved definition.
>> Derefter hver andet element er defineret som summen af ​​n minus 1, og n minus 2.
Så det tredje element ville være 0 plus 1 er 1.
Og så det fjerde element ville være det andet element, 1,
plus det tredje element, 1.
Og det ville være 2.
Og så videre og så videre.
>> Så i dette tilfælde, har vi to base-sager.
Hvis n er lig med 1, returnere 0.
Hvis n er lig med 2, returnere 1.
Ellers returnerer Fibonacci n minus 1 plus Fibonacci n minus 2.
>> Så det er flere baser sager.
Hvad med flere rekursive tilfælde?
Tja, der er noget kaldet Collatz formodninger.
Jeg har ikke tænkt mig at sige, du ved, hvad det er,
fordi det er faktisk vores endelige problem for denne særlige video.
Og det er vores øvelse at arbejde på sammen.
>> Så her er hvad Collatz formodninger is--
det gælder for ethvert positivt heltal.
Og det gætter på, at det er altid muligt at komme tilbage
til 1, hvis du følger disse trin.
Hvis n er 1, stop.
Vi har fået tilbage til 1, hvis n er 1.
>> Ellers skal du gå gennem denne processen igen på n divideres med 2.
Og se om du kan komme tilbage til en.
Ellers, hvis n er ulige, gå gennem denne proces igen på 3n + 1,
eller 3 gange n plus 1.
Så her har vi en enkelt base case.
Hvis n er lig med 1, stop.
Vi laver ikke noget mere rekursion.
>> Men vi har to rekursive tilfælde.
Hvis n er lige, vi gør en rekursiv tilfælde, kaldte n divideres med 2.
Hvis n er ulige, gør vi en anden rekursive tilfælde på 3 gange n plus 1.
>> Og så målet for denne video er at tage en anden, pause videoen,
og prøv og skrive dette rekursiv funktion Collatz
hvor du passerer en værdi n, og Det beregner, hvor mange skridt det
tager at komme til 1, hvis du starter fra n og du følger disse trin op ovenfor.
Hvis n er 1, det tager 0 trin.
Ellers går det til tager et skridt plus imidlertid
mange skridt det tager enten n divideret med 2, hvis n er lige, eller 3n plus 1
hvis n er ulige.
>> Nu har jeg sat op på skærmen her et par test ting for dig,
et par test sager for dig, for at se hvad disse forskellige Collatz tal er,
og også en illustration af de skridt,
nødt til at være gået igennem så kan du slags se denne proces i aktion.
Så hvis n er lig med 1, Collatz n er 0.
Du behøver ikke at gøre noget at komme tilbage til en.
Du er der allerede.
>> Hvis n er 2, det tager et skridt for at komme til 1.
Du starter med 2.
Tja, 2 er ikke lig med 1.
Så det vil være et skridt plus dog mange skridt det
tager på n divideres med 2.
>> 2 divideret med 2 er 1.
Så det tager et skridt plus dog mange trin, det tager for en.
1 tager nul trin.
>> For 3, som du kan se, er der involveret et par skridt.
Du går fra 3.
Og så skal du gå til 10, 5, 16, 8, 4, 2, 1.
Det tager syv trin til at komme tilbage til 1.
Og som du kan se, er der en par andre prøvesager her
at teste dit program.
Så igen, pause videoen.
Og jeg vil gå hoppe tilbage nu hvad selve processen er her,
hvad denne formodning er.
>> Se om du kan finde ud af hvordan man definerer Collatz n
så den beregner, hvor mange skridt det tager at komme til 1.
Så forhåbentlig har du sat på pause videoen og du er ikke bare venter på mig
at give dig svaret her.
Men hvis du er, godt, her er svaret alligevel.
>> Så her er en mulig definition af Collatz funktionen.
Vores base case-- hvis n er lig med 1, vender vi tilbage 0.
Det tager ikke nogen skridt til at komme tilbage til en.
>> Ellers har vi to rekursive cases-- én for lige numre og en for ulige.
Den måde jeg teste for lige numre er at kontrollere, om n mod 2 er lig med 0.
Dette er dybest set igen, stille spørgsmålet,
hvis du huske, hvad mod is-- hvis jeg kløft n med 2 er der ingen resten?
Det ville være et lige antal.
>> Og så hvis n mod 2 er lig med 0 er test er det et lige antal.
Hvis ja, jeg ønsker at vende tilbage 1, fordi dette er absolut
tager et skridt plus Collatz af hvad nummer er halvdelen af ​​mig.
Ellers vil jeg vende tilbage 1 plus Collatz af 3 gange n plus 1.
Det var den anden rekursiv skridt, vi
kunne tage at beregne Collatz-- antallet af trin
det tager at komme tilbage 1 gives et nummer.
Så forhåbentlig, dette eksempel gav dig en lille smule
af en smag af rekursive procedurer.
Forhåbentlig du synes kode er en lidt smukkere hvis de gennemføres
i en elegant, rekursiv måde.
Men selv om det ikke, rekursion er en virkelig kraftfuldt værktøj alligevel.
Og så det er helt sikkert noget at få dit hoved rundt,
fordi du vil være i stand til at skabe pretty cool programmer ved hjælp rekursion
som ellers kunne være kompliceret at skrive hvis du bruger loops og iteration.
Jeg er Doug Lloyd.
Det er CS50.