[Muziek] 

DOUG LLOYD: Je denkt waarschijnlijk dat code wordt alleen gebruikt om een ​​taak te volbrengen. Je schrijft het uit. Het doet iets. Dat is vrij veel. 

U compileren. U start het programma. Je bent goed om te gaan. 

Maar geloof het of niet, als u coderen voor een lange tijd, je eigenlijk zou kunnen komen te zien code als iets dat is prachtig. Het lost een probleem een zeer interessante manier, of er is gewoon iets echt keurige over de manier waarop het eruit ziet. Je zou kunnen lachen bij mij, maar het is waar. En recursie is een manier om een ​​soort van krijgen dit idee van mooie, elegante ogende code. Het lost problemen op manieren die zijn interessant, gemakkelijk te visualiseren, en verrassend kort. 

De manier waarop recursie werken is een recursieve functie wordt gedefinieerd als een functie die oproepen zich als onderdeel van de uitvoering. Dat lijkt misschien een beetje vreemd, en we zullen een beetje zien over hoe dit werkt in een moment. Maar nogmaals, deze recursieve procedures ga zo elegant te zijn omdat ze gaan dit probleem op te lossen zonder hebben al deze andere functies of deze lange lussen. Je zult zien dat deze recursieve procedures zullen zo kort kijken. En ze echt gaan maken uw code er een stuk mooier. 

Ik zal u een voorbeeld geven dit om te zien hoe een recursieve procedure kan worden vastgesteld. Dus als je vertrouwd zijn met deze bent van wiskunde klasse vele jaren geleden, Er is iets genaamd de faculteit-functie, die meestal aangeduid als een uitroepteken, die is gedefinieerd over alle positieve gehele getallen. En de manier waarop n factorial berekend wordt u alle vermenigvuldigen de getallen kleiner dan of gelijk aan n together-- alle getallen lager dan of gelijk aan n samen. 

Dus 5 faculteit is 5 keer 4 maal 3 keer 2 keer 1. En 4 faculteit is 4 keer 3 keer 2 keer 1 enzovoort. Je krijgt het idee. 

Als programmeurs, doen we niet Gebruik n, uitroepteken. Dus we de faculteit definiëren functie feit n. En we zullen faculteit gebruiken voor het maken een recursieve oplossing voor een probleem. En ik denk dat je zou kunnen vinden dat het een veel meer visueel aantrekkelijk dan de iteratieve versie van deze, waarvan We zullen ook een kijkje nemen op in een moment. 

Dus hier zijn een paar facts-- woordspeling intended-- over de factorial-- faculteit-functie. De faculteit van 1, zoals ik al zei, is 1. De faculteit van 2 is 2 keer 1. De faculteit van 3 3 tijden 2 keer 1, enzovoorts. We spraken over 4 en 5 al. 

Maar te kijken naar dit, is dit niet waar is? Wordt niet faculteit van 2 net 2 maal de faculteit van 1? Ik bedoel, de faculteit van 1: 1. Dus waarom kunnen we zeggen alleen dat, aangezien faculteit van 2 is 2 maal 1, het is eigenlijk gewoon 2 keer de faculteit van 1? 

En dan de uitbreiding van dat idee, is de faculteit van 3 slechts 3 maal de faculteit van 2? En de faculteit van 4 is 4 keer de faculteit van 3, enzovoorts? In feite is de faculteit van een willekeurig aantal kan gewoon Als we worden uitgedrukt soort van te voeren dit uit voor altijd. We kunnen soort generaliseren de faculteit probleem aangezien het n keer de faculteit van n minus 1. Het is n maal het product van alle nummers minder dan ik. 

Dit idee, deze veralgemening van het probleem, stelt ons in staat om recursief definiëren de faculteit-functie. Wanneer u een functie definieert recursief, er is twee dingen die moeten een deel van het zijn. Je nodig hebt om een ​​zogenaamde base case, die, als je het triggeren, zal het recursieve proces te stoppen. 

Anders, een functie die oproepen itself-- zoals je misschien imagine-- zou kunnen blijven vertellen. Functie noemt de functie roept de functie oproepen de functie roept de functie. Als u niet beschikt over een manier hebben om het te stoppen, je programma zal effectief worden geplakt in een oneindige lus. Het zal uiteindelijk crashen, want het zal uit het geheugen draaien. Maar dat is naast het punt. 

We moeten een andere manier om te stoppen hebben dingen naast ons programma crashen, omdat een programma dat crasht is waarschijnlijk niet mooi of elegant. En dus hebben we dit de basis geval noemen. Dit is een eenvoudige oplossing een probleem dat stopt het recursieve proces optreedt. Dus dat is een deel van een recursieve functie. 

Het tweede deel is de recursieve geval. En dit is waar de recursie zal daadwerkelijk plaatsvinden. Dit is waar de functie zal zichzelf noemen. 

Het zal zich niet precies noemen Op dezelfde manier werd het genoemd. Het zal een lichte variatie dat maakt het probleem is het proberen om een ​​piepklein beetje kleiner te lossen. Maar het gaat over het algemeen van de bok oplossing van de bulk van de oplossing naar een ander gesprek langs de lijn. 

Welke van deze looks zoals de base case hier? Welke van deze lijkt op het eenvoudigste oplossing voor een probleem? We hebben een heleboel faculteiten, en we konden blijven gaan on-- 6, 7, 8, 9, 10, enzovoort. 

Maar een van deze ziet eruit als een goede zaak naar de basis geval te zijn. Het is een heel eenvoudige oplossing. We hoeven niet om iets bijzonders te doen. 

De faculteit van 1 ligt op slechts 1. We hoeven niet elke doen vermenigvuldigen helemaal. Het lijkt alsof we gaan om te proberen dit probleem op te lossen, en we naar de halte nodig Recursion ergens, waarschijnlijk willen we stoppen wanneer we naar 1. We willen niet stoppen voordat dat. 

Dus als we het definiëren onze faculteit-functie, hier is een skelet voor hoe we dat zouden kunnen doen. We moeten aansluiten in die twee things-- de base case en het recursieve geval. Wat is de base case? Als n gelijk is aan 1, dat is terug 1-- een heel eenvoudig probleem op te lossen. 

De faculteit van 1: 1. Het is niet 1 keer niets. Het is slechts 1. Het is een heel eenvoudig feit. En zodat u onze basis geval zijn. Als we voorbij 1 in deze functie, zullen we gewoon terug 1. 

Wat is de recursieve geval waarschijnlijk eruit? Voor elk ander nummer behalve 1, wat is het patroon? Nou, als we nemen de faculteit van n, het n keer de faculteit van n minus 1. 

Als we het nemen van de faculteit van 3, het 3 keer de faculteit van 3 minus 1, of 2. En dus als we niet kijken 1, anders return n keer de faculteit van n minus 1. Het is vrij eenvoudig. 

En omwille van het hebben lichtjes schonere en meer elegante code, weten dat als we één regel lussen of single-lijn voorwaardelijke takken, we kunnen ontdoen van alle accolades om hen heen. Dus we kunnen deze te consolideren om dit. Deze heeft dezelfde Deze functionaliteit. 

Ik ben gewoon het wegnemen van de krullend bretels, want er is maar één regel binnenzijde van die voorwaardelijke sprongen. Dus deze gedragen zich identiek. Als n gelijk is aan 1, 1 terug. Anders terug n keer de faculteit van n minus 1. Dus we maken het probleem kleiner. Als n begint als 5, we gaan terug 5 keer de faculteit van 4. En we zullen zien in een minuut als we praten over de oproep stack-- in een andere video waar we praten over de noemen stack-- we leren waarom juist dit proces werkt. 

Maar terwijl faculteit van 5 zegt: terug 5 keer faculteit van 4 en 4 gaat zeggen, OK, goed, terug 4 maal de faculteit van 3. En zoals je kunt zien, zijn we soort naderen 1. We zijn steeds dichter en dichter bij die basisgeval. 

En zodra we de base case hit, alle voorgaande functies het antwoord dat ze op zoek waren. Faculteit van 2 zei terugkeer 2 maal de faculteit van 1. Nou, faculteit van 1 rendementen 1. Zodat de oproep faculteit van 2 kan 2 keer 1 terug, en geef die terug naar faculteit van 3, die om dat resultaat wacht. 

En dan kan het berekenen het resultaat, 3 keer 2 is 6, en geef het terug naar faculteit van 4. En nogmaals, we hebben een video op de oproep stack wanneer dit een beetje wordt geïllustreerd meer dan wat ik nu zeg. Maar dit is het. Dit alleen is de oplossing voor berekenen van de faculteit van een getal. 

Het is slechts vier regels code. Dat is wel cool, toch? Het is een beetje sexy. 

Dus in het algemeen, maar niet altijd een recursieve functie kan een lus in een te vervangen niet-recursieve functie. Dus hier, naast elkaar, is de iteratieve versie van de faculteit-functie. Beide berekenen precies hetzelfde. 

Beiden bereken de faculteit van n. De versie links recursie gebruikt om het te doen. De versie rechts iteratie gebruikt om het te doen. 

En bericht, we moeten verklaren een variabele een integer product. En dan hebben we lus. Zolang n groter is dan 0, we houden dat product door n vermenigvuldigen en aflopende n totdat berekenen we het product. Dus deze twee functies, opnieuw, doen precies hetzelfde. Maar ze doen het niet in precies dezelfde manier. 

Nu is het mogelijk om hebben meer dan een base case of meerdere recursief geval, afhankelijk op wat uw functie probeert te doen. U bent niet per se alleen beperkt tot een enkele base case of een enkele recursieve case. Dus een voorbeeld van iets meerdere base cases misschien dit-- de Fibonacci getallenreeks. 

U herinnert zich misschien uit basisschool dagen dat de Fibonacci-reeks is gedefinieerd zoals dit-- het eerste element is 0. Het tweede element is 1. Deze beide zijn per definitie. 

Dan elke andere wordt gedefinieerd de som van n en n 1 min 2 min. Dus het derde element zou 0 1 plus 1 is. En dan de vierde element zou het tweede element, 1 zijn, plus het derde element, 1. En dat zou 2. En zo voort en zo verder. 

Dus in dit geval hebben we twee base gevallen. Als n gelijk is aan 1, 0 terug. Als n gelijk is aan 2, terug 1. Anders terugkeer van Fibonacci n plus minus 1 Fibonacci n minus 2. 

Dus dat is meerdere base gevallen. Hoe zit het met meerdere recursieve gevallen? Nou, er is iets genaamd de Collatz vermoeden. Ik ga niet zeggen, je weet wat dat is, want het is eigenlijk onze laatste probleem voor deze video. En het is onze oefening samen te werken. 

Dus hier is wat de Collatz vermoeden is-- het geldt voor elk positief geheel getal. En speculeert dat het altijd mogelijk om terug te krijgen 1 als u de volgende stappen. Wanneer n is 1, stoppen. We moeten terug naar 1 als n 1 is. 

Anders, door deze Werkwijze weer n gedeeld door 2. En kijk of je kunt terug naar 1. Anders, als n oneven is, gaan door Dit proces weer 3n plus 1, of 3 maal n plus 1. Dus hier hebben we een enkele base case. Als n gelijk is aan 1, stoppen. We zijn niet te doen meer recursie. 

Maar we hebben twee recursieve gevallen. Als n even is, doen we een recursieve geval roeping n gedeeld door 2. Als n oneven is, doen we een andere recursieve geval op 3 maal n plus 1. 

En zo het doel van deze video is om een ​​tweede te nemen, de video te pauzeren, en probeer dit schrijf recursieve functie Collatz waar u passeren een waarde n en berekent hoeveel stappen die zij neemt tot 1 te krijgen als u begint met n en volg je die stappen boven. Wanneer n is 1, duurt 0 stappen. Anders gaat het om een stap plus nochtans vele stappen die nodig aan beide n gedeeld door 2 als n even of 3n plus 1 als n oneven is. 

Nu, ik heb op het scherm zetten hier een paar van de test dingen voor je, een paar testen gevallen voor u, om te zien Wat deze verschillende Collatz getallen, alsmede een illustratie van de stappen die moet door middel van dus je kunt om zijn gegaan soort van zien dit proces in actie. Als n gelijk is aan 1, Collatz van n is 0. Je hoeft niet te doen alles om terug te gaan naar 1. Je bent er al. 

Wanneer n 2 is, duurt een stap naar 1 te krijgen. Je begint met 2. Welnu, 2 niet gelijk is aan 1. Dus het gaat om één stap plus hoeveel stappen die zij neemt n gedeeld door 2. 

2 gedeeld door 2: 1. Dus het duurt een stap plus nochtans vele stappen die nodig is om 1. 1 neemt nul stappen. 

3, zoals u kunt zien, is er een flink aantal stappen die betrokken. Je gaat van 3. En dan ga je naar 10, 5, 16, 8, 4, 2, 1. Het duurt zeven stappen om terug te keren naar 1. En zoals je kunt zien, is er een paar andere testcases hier aan het testen van uw programma. Dus nogmaals, pauzeren de video. En ik ga terugspringen nu Wat het eigenlijke proces hier wat dit vermoeden is. 

Kijk of je kunt achterhalen hoe Collatz n definiëren zodat het berekent hoeveel de stappen die het duurt om 1 te krijgen. Dus hopelijk, u de video onderbroken hebben en je bent niet alleen op me te wachten u hier het antwoord te geven. Maar als je, nou ja, hier is het antwoord toch. 

Dus hier is een mogelijke definitie het Collatz functie. Onze basis case-- als n gelijk aan 1, we terugkeren 0. Het bevat geen te nemen stappen om terug te keren naar 1. 

Anders, we hebben twee recursieve cases-- één voor de even nummers en één voor de oneven. De manier waarop ik te testen voor even getallen is om te controleren of n mod 2 gelijk is aan 0. Dit is in principe weer, de vraag te stellen, als je herinneren wat mod is-- als ik kloof n door 2 is er geen rest? Dat zou een even getal. 

En dus als n mod 2 is gelijk aan 0 is testen is dit een even getal. Als dat zo is, wil ik terugkeren 1, want dit is zeker het nemen van een stap plus Collatz van welk getal is de helft van mij. Anders, ik wil terugkeren 1 plus Collatz 3 keer n plus 1. Dat was de andere recursieve stap die we kunnen nemen om het te berekenen Collatz-- het aantal stappen het duurt om terug te krijgen 1 een nummer. Dus hopelijk, dit voorbeeld gaf je een beetje van een voorproefje van recursieve procedures. Hopelijk je denkt code is een beetje mooier indien uitgevoerd in een elegante, recursieve manier. Maar zelfs indien niet, recursie is een echt krachtige tool toch. En dus is het zeker iets om je hoofd rond te krijgen, want je zult in staat zijn om te creëren pretty cool programma's met behulp van recursie die anders ingewikkeld te schrijven als je met behulp van loops en iteratie. Ik ben Doug Lloyd. Dit is CS50.