[Speel van musiek] 

DOUG LLOYD: Jy dink waarskynlik dat kode is net gebruik om 'n taak uit te voer. Jy skryf dit uit. Dit doen iets. Dit is pretty much dit. 

Jy stel nie. Jy loop die program. Jy is goed om te gaan. 

Maar glo dit of nie, as jy kode vir 'n lang tyd, jy eintlik kan kom om te sien kode as iets wat mooi. Dit los 'n probleem in 'n baie interessante manier, of daar is net iets wat regtig netjiese oor die manier waarop dit lyk. Jy kan lag by my, maar dit is waar. En rekursie is een manier om soort van kry hierdie idee pragtige, elegante-soek-kode. Dit los probleme op maniere wat is interessant, maklik om te visualiseer, en verrassend kort. 

Die manier waarop rekursie werke is, 'n rekursiewe funksie word gedefinieer as 'n funksie wat roep homself as deel van die uitvoering daarvan. Dit lyk dalk 'n bietjie vreemd, en ons sal 'n bietjie kyk oor hoe dit werk in 'n oomblik. Maar weereens, hierdie rekursiewe prosedures gaan so elegant te wees want hulle gaan om hierdie probleem op te los sonder met al hierdie ander funksies of die lang lusse. Jy sal sien dat hierdie rekursiewe prosedures gaan so kort lyk. En hulle het regtig gaan maak jou kode lyk baie mooier. 

Ek sal jou 'n voorbeeld te gee van hierdie om te sien hoe 'n rekursiewe prosedure kan gedefinieer word. So as jy vertroud is met hierdie is van wiskunde klas baie jare gelede, Daar is iets genoem die faktoriaal funksie, wat gewoonlik aangedui as 'n uitroepteken, wat word gedefinieer as alle positiewe heelgetalle. En die manier waarop N faktoriaal bereken is jy al vermenigvuldig die nommers minder as of gelyk aan N saam op al die heelgetalle minder as of gelyk aan N saam. 

So 5 faktoriaal is 5 keer 4 keer 3 keer 2 keer 1. En 4 faktoriaal is 4 keer 3 keer 2 keer 1 en so aan. Jy kry die idee. 

As programmeerders, ons doen nie gebruik n, uitroepteken. So sal ons die faktoriaal definieer funksie as 'n feit van n. En ons sal faktoriaal gebruik om te skep 'n rekursiewe oplossing vir 'n probleem. En ek dink jy kan vind dat dit 'n baie meer visueel beroep as die iteratiewe weergawe van hierdie, wat Ons sal ook 'n blik op in 'n oomblik. 

So hier is 'n paar van die facts-- woordspeling intended-- oor die factorial-- faktoriaal funksie. Die faktoriaal van 1, soos ek gesê het, is 1. Die faktoriaal van 2 is 2 keer 1. Die faktoriaal van 3 is 3 keer 2 keer 1, en so aan. Ons het gepraat oor 4 en 5 reeds. 

Maar kyk na hierdie, is dit nie so nie? Is dit nie faktoriaal van 2 net 2 keer die faktoriaal van 1? Ek bedoel, die faktoriaal van 1 is 1. So hoekom kan ons nie sê net dat, sedert faktoriaal van 2 is 2 keer 1, Dit is regtig net 2 keer die faktoriaal van 1? 

En dan brei die idee, is nie die faktoriaal van 3 net 3 keer die faktoriaal van 2? En die faktoriaal van 4 is 4 keer die faktoriaal van 3, en so aan? Trouens, die faktoriaal van enige aantal kan net as ons uitgedruk soort van voer dit uit vir ewig. Ons kan soort van veralgemeen die faktoriaal probleem as dit is n keer die faktoriaal van N minus 1. Dit is n keer die produk van al die getalle minder as ek. 

Hierdie idee, hierdie veralgemening van die probleem, kan ons rekursief definieer die faktoriaal funksie. Wanneer jy 'n funksie te definieer rekursief, daar is twee dinge wat nodig is om 'n deel van dit te wees. Jy moet iets genoem 'n basis geval, wat, wanneer jy dit aktiveer, sal die rekursiewe proses te stop. 

Anders, 'n funksie wat roep itself-- as jy dalk imagine-- kon vir ewig gaan. Funksie noem die funksie noem die funksie oproepe die funksie noem die funksie. As jy nie 'n manier het om dit te stop, jou program sal effektief vas teen 'n oneindige lus. Dit sal uiteindelik crash, want dit sal uit die geheue uit te voer. Maar dit is langs die punt. 

Ons moet 'n ander manier om te stop het dinge behalwe ons program gekraak, omdat 'n program wat ineenstortings is waarskynlik nie mooi of elegant. En so het ons dit die basis geval noem. Dit is 'n eenvoudige oplossing om 'n probleem wat tot stilstand kom die rekursiewe proses te voorkom. So dit is 'n deel van 'n rekursiewe funksie. 

Die tweede deel is die rekursiewe geval. En dit is waar die rekursie sal eintlik plaasvind. Dit is waar die funksie sal self noem. 

Dit sal hom nie in presies noem op dieselfde manier het dit genoem. Dit sal 'n effense variasie wees dit maak die probleem is dit probeer om 'n bietjie kleiner Teeny op te los. Maar dit gaan oor die algemeen die bok van die oplossing van die grootste deel van die oplossing na 'n ander oproep in die ry. 

Watter van hierdie lyk soos die basis geval hier? Watter een van hierdie lyk soos die eenvoudigste oplossing vir 'n probleem? Ons het 'n klomp van die factorials, en ons kon voortgaan gaan on-- 6, 7, 8, 9, 10, en so aan. 

Maar een van hierdie lyk soos 'n goeie saak na die basis geval te wees. Dit is 'n baie eenvoudige oplossing. Ons het nie iets spesiaals te doen. 

Die faktoriaal van 1 is net 1. Ons het nie nodig om enige te doen vermenigvuldiging at all. Dit lyk asof ons gaan om te probeer en hierdie probleem op te los, en ons na die stop nodig rekursie iewers, waarskynlik wil ons om te stop dit wanneer ons by 1. Ons wil nie om te stop voor dit. 

So as ons definieer ons faktoriaal funksie, hier is 'n geraamte vir hoe ons dit kan doen. Ons moet prop in daardie twee things-- die basis geval en die rekursiewe geval. Wat is die basis geval? As n is gelyk aan 1, terugkeer 1-- dis 'n baie eenvoudige probleem op te los. 

Die faktoriaal van 1 is 1. Dit is nie 1 keer nie. Dis net 1. Dit is 'n baie maklike feit. En so kan ons basis geval wees. As ons verby 1 na hierdie funksie, sal ons net terug 1. 

Wat is die rekursiewe geval waarskynlik lyk? Vir elke ander getal Behalwe 1, wat is die patroon? Wel, as ons neem die faktoriaal van n, dit is n keer die faktoriaal van N minus 1. 

As ons neem die faktoriaal van 3, dit is 3 maal die faktoriaal van 3 minus 1, of 2. En so as ons nie op soek na 1, anders terugkeer N keer die faktoriaal van N minus 1. Dit is redelik eenvoudig. 

En ter wille van 'n effens skoner en meer elegante kode, weet dat as ons enkel-lyn loops of enkel-line voorwaardelike takke, ons kan ontslae te raak van al die krulhakies rondom hulle. So kan ons dit konsolideer om hierdie. Dit het presies dieselfde funksie soos hierdie. 

Ek is net weg te neem die krullerige draadjies, want daar is net een lyn binnekant van die voorwaardelike takke. So het hierdie gedra identies. As n is gelyk aan 1, terug 1. Anders terugkeer N tye die faktoriaal van N minus 1. Ons is so maak die probleem kleiner. As n begin as 5, gaan ons terugkeer 5 keer die faktoriaal van 4. En ons sal sien in 'n minuut wanneer ons praat oor die oproep stack-- in 'n ander video waar ons praat oor die noem stack-- ons sal leer oor hoekom juis hierdie proses werk. 

Maar terwyl faktoriaal van 5 sê terugkeer 5 keer faktoriaal van 4, en 4 gaan om te sê, OK, goed, terugkeer 4 keer die faktoriaal van 3. En soos jy kan sien, is ons soort van nader 1. Ons kry nader en nader aan daardie basis geval. 

En sodra ons die basis geval getref, al die vorige funksies het die antwoord hulle soek. Faktoriaal van 2 sê terugkeer 2 keer die faktoriaal van 1. Wel, faktoriaal van 1 opbrengste 1. So het die oproep vir faktoriaal van 2 kan 2 keer 1 terugkeer, en gee dat terug na faktoriaal van 3, wat vir daardie gevolg wag. 

En dan kan dit te bereken die resultaat, 3 keer 2 is 6, en gee dit terug na faktoriaal van 4. En weer, ons het 'n video op die oproep stapel waar dit 'n bietjie geïllustreer meer as wat ek nou sê. Maar dit is dit. Dit alleen is die oplossing vir die berekening van die faktoriaal van 'n aantal. 

Dit is slegs vier reëls van die kode. Dit is pretty cool, reg? Dit is soort van sexy. 

So in die algemeen, maar nie altyd 'n rekursiewe funksie kan 'n lus in 'n plek van nie-rekursiewe funksie. So hier, langs mekaar, is die iteratiewe weergawe van die faktoriaal funksie. Beide van hierdie bereken presies dieselfde ding. 

Hulle het albei bereken die faktoriaal van n. Die weergawe aan die linkerkant gebruik rekursie om dit te doen. Die weergawe op die regte gebruik iterasie om dit te doen. 

En kennis, ons het om te verklaar 'n veranderlike 'n heelgetal produk. En dan het ons lus. So lank as N groter as 0, ons hou dat die produk deur te vermenigvuldig N en decrementing N totdat Ons bereken die produk. So het hierdie twee funksies, weer, doen presies dieselfde ding. Maar hulle doen dit nie in presies dieselfde manier. 

Nou, is dit moontlik om het meer as een basis geval of meer as een rekursiewe geval, afhangende oor wat jou funksie is om te probeer doen. Jy is nie noodwendig net beperk tot 'n enkele basis geval of 'n enkele rekursiewe geval. So 'n voorbeeld van iets met verskeie base gevalle dalk this-- die Fibonacci getal ry. 

Jy kan onthou uit laerskool dae dat die Fibonacci-ry word gedefinieer soos this-- die eerste element is 0. Die tweede element is 1. Beide van hulle is net per definisie. 

Dan elke ander element gedefinieer as die som van N minus 1 en N minus 2. So die derde element sou wees 0 plus 1 is 1. En dan die vierde element sou die tweede element, 1 wees, plus die derde element, 1. En dit sou wees 2. En so aan en so aan. 

So in hierdie geval, het ons twee base gevalle. As n is gelyk aan 1, terugkeer 0. As n is gelyk aan 2, terug 1. Anders, terugkeer Fibonacci van N minus 1 plus Fibonacci van N minus 2. 

So dit is verskeie base gevalle. Wat van veelvuldige rekursiewe gevalle? Wel, daar is iets genoem die Collatz veronderstelling. Ek gaan nie om te sê, jy weet wat dit is, want dit is eintlik ons ​​finale probleem vir hierdie spesifieke video. En dit is ons oefening om saam te werk. 

So hier is wat die Collatz veronderstelling is-- dit is van toepassing op elke positiewe heelgetal. En dit bespiegel dat dit altyd moontlik om terug te kry 1 as jy volg hierdie stappe. Indien n '1, stop. Ons het terug na 1 as n 1. 

Andersins, gaan deur hierdie proses weer op N gedeel deur 2. En kyk of jy kan terug te kry om 1. Anders, as n onewe, gaan deur hierdie proses weer op 3n plus 1, of 3 keer n plus 1. So hier het ons 'n enkele basis geval. As n is gelyk aan 1, stop. Ons is nie om enige meer rekursie. 

Maar ons het twee rekursiewe gevalle. As n ewe, ons doen een rekursiewe geval, bel N gedeel deur 2. As n onewe, ons doen 'n ander rekursiewe geval op 3 keer n plus 1. 

En so het die doel vir hierdie video is om 'n tweede neem, breek die video, en probeer en skryf dit rekursiewe funksie Collatz waar jy slaag in 'n waarde n, en dit bereken hoeveel stappe dit neem om 1 te kry as jy begin van N en jy volg die stappe bo. Indien n '1, neem dit 0 stappe. Andersins, dit gaan neem 'n stap plus egter baie stappe wat dit neem op óf N gedeel deur 2 as n ewe is, of 3n plus 1 As n onewe. 

Nou, ek het op die skerm hier sit 'n paar van die toets dinge vir jou, 'n paar van toetse gevalle vir jou, om te sien wat hierdie verskillende Collatz getalle is, en ook 'n illustrasie van die stappe wat moet deur sodat jy kan om weg soort van sien hierdie proses in aksie. So as N is gelyk aan 1, Collatz van N is 0. Jy hoef nie te doen niks om terug te kry om 1. Jy is reeds daar. 

As N is 2, dit neem een stap na 1 te kry. Jy begin met 2. Wel, 2 is nie gelyk aan 1. So dit gaan 'n stap wees plus egter baie stappe dit neem op N gedeel deur 2. 

2 gedeel deur 2 is 1. So dit neem 'n stap plus egter baie stappe wat dit neem vir 1. 1 neem nul stappe. 

Vir 3, soos jy kan sien, is daar nogal 'n paar stappe wat betrokke is. Jy gaan van 3. En dan gaan jy na 10, 5, 16, 8, 4, 2, 1. Dit neem sewe stappe om terug te kry om 1. En soos jy kan sien, is daar 'n paar ander toets gevalle hier om te toets jou program. So weer, breek die video. En ek gaan spring nou terug om wat die werklike proses is hier, wat hierdie vermoede is. 

Kyk of jy kan uitvind hoe om Collatz van N definieer sodat dit bereken hoeveel stappe wat dit neem om 1 te kry. So hopelik jy die video gestop het en jy is nie net wag vir my om vir jou die antwoord hier gee. Maar as jy, wel, Hier is die antwoord in elk geval. 

So hier is 'n moontlike definisie van die Collatz funksie. Ons basis case-- as n gelyk aan 1, ons terugkeer 0. Dit maak nie neem stappe om terug te kry om 1. 

Andersins, het ons twee rekursiewe cases-- een vir ewe getalle en een vir vreemd. Die manier waarop ek toets vir ewe getalle is om te kyk of n mod 2 is gelyk aan 0. Dit is basies, weer, vra die vraag, as jy onthou wat mod is-- as ek verdeel N 2 deur daar is geen res? Dit sou 'n ewe getal wees. 

En so as N mod 2 is gelyk aan 0 is toets is dit 'n ewe getal. As dit so is, wil ek teruggaan 1, want dit is beslis neem 'n stap plus Collatz van watter getal is die helfte van my. Anders, ek wil om terug te keer 1 plus Collatz van 3 keer n plus 1. Dit was die ander rekursiewe stap dat ons kan neem om die te bereken Collatz-- die aantal stappe dit neem om terug te kry 1 'n nommer. So hopelik hierdie voorbeeld het jy 'n bietjie van 'n voorsmakie van rekursiewe prosedures. Hopelik jy dink kode is 'n bietjie mooier indien geïmplementeer in 'n elegante, rekursiewe manier. Maar selfs indien nie, is 'n rekursie regtig kragtige instrument nietemin. En so is dit beslis iets om jou kop om te kry, omdat jy sal in staat wees om te skep pretty cool programme met behulp van rekursie wat anders kan komplekse te skryf wees As jy met behulp van lusse en iterasie. Ek is Doug Lloyd. Dit is CS50.