Share
Sommige problemen worden natuurlijker opgelost met behulp van recursie. Een reeks zoals de Fibonacci-reeks heeft bijvoorbeeld een recursieve definitie. Elk nummer in de reeks is de som van de vorige twee getallen in de reeks. Problemen waarvoor u een boomachtige gegevensstructuur moet bouwen of doorkruisen, kunnen ook met recursie worden opgelost. Jezelf trainen om recursief te denken, geeft je een krachtige vaardigheid om dergelijke problemen aan te pakken.
In deze tutorial zal ik stap voor stap verschillende recursieve functies doornemen om te zien hoe ze werken en je technieken laten zien die je kunt gebruiken om systematisch recursieve functies te definiëren.
Een recursief gedefinieerde functie is een functie die wordt gedefinieerd in termen van een eenvoudigere versie van zichzelf. Dit is een vereenvoudigd voorbeeld:
functie doA (n) ... doA (n-1);
Om te begrijpen hoe recursie conceptueel werkt, zullen we een voorbeeld bekijken dat niets met code te maken heeft. Stel je voor dat je verantwoordelijk bent voor het beantwoorden van telefoontjes op het werk. Omdat dit een druk bedrijf is, heeft uw telefoon meerdere telefoonlijnen, zodat u tegelijkertijd met meerdere gesprekken kunt jongleren. Elke telefoonlijn is een knop op de ontvanger en wanneer er een oproep binnenkomt, knippert de knop. Vandaag, wanneer u aankomt om te werken en de telefoon aanzet, knipperen er vier lijnen tegelijkertijd. Dus je gaat aan de slag om alle oproepen te beantwoorden.
Je neemt regel één op en zegt 'houd vast'. Vervolgens pak je regel twee en zet je ze in de wacht. Vervolgens neem je lijn drie op en zet je ze in de wacht. Eindelijk de vierde regel die u beantwoordt en met de beller spreekt. Als u klaar bent met de vierde beller, hangt u op en neemt u de derde oproep aan. Als je klaar bent met de derde oproep, hang je op en neem je de tweede oproep aan. Wanneer u klaar bent met het tweede gesprek, hangt u op en neemt u het eerste gesprek op. Als je klaar bent, kun je eindelijk de telefoon neerleggen.
Elk van de telefoontjes in dit voorbeeld is als een recursieve oproep in een functie. Wanneer u wordt gebeld, wordt deze op de call stack geplaatst (in code speak). Als u een gesprek niet meteen kunt voltooien, zet u het gesprek in de wacht. Als u een functieaanroep hebt die niet onmiddellijk kan worden geëvalueerd, blijft deze in de oproepstapel. Wanneer u een oproep kunt beantwoorden, wordt deze opgehaald. Wanneer uw code een functieaanroep kan evalueren, wordt deze uit de stapel gehaald. Houd deze analogie in gedachten terwijl je kijkt naar de volgende codevoorbeelden.
Alle recursieve functies hebben een basisscenario nodig, zodat ze worden beëindigd. Het toevoegen van een basisscenario aan onze functie betekent echter niet dat het niet oneindig kan worden uitgevoerd. De functie moet een stap hebben om ons dichter bij het basisscenario te brengen. Laatste is de recursieve stap. In de recursieve stap wordt het probleem gereduceerd tot een kleinere versie van het probleem.
Stel dat je een functie hebt die de getallen optelt van 1 tot n. Bijvoorbeeld, als n = 4, somt het 1 + 2 + 3 + 4.
Eerst bepalen we het basisscenario. Het vinden van het basisscenario kan ook worden gezien als het vinden van de casus waarbij het probleem zonder recursie kan worden opgelost. In dit geval is het wanneer n gelijk is aan nul. Nul heeft geen onderdelen, dus onze recursie kan stoppen wanneer we 0 bereiken.
Bij elke stap trekt u er een af van het huidige getal. Wat is de recursieve casus? Het recursieve geval is de functiesom die wordt aangeroepen met het gereduceerde aantal.
function sum (num) if (num === 0) return 0; else return num + sum (- num) sum (4); // 10
Dit is wat er gebeurt bij elke stap:
Dit is een andere manier om te bekijken hoe de functie elke oproep verwerkt:
som (4) 4 + som (3) 4 + (3 + som (2)) 4 + (3 + (2 + som (1))) 4 + (3 + (2 + (1 + som (0)) )) 4 + (3 + (2 + (1 + 0))) 4 + (3 + (2 + 1)) 4 + (3 + 3) 4 + 6 10
Het argument moet in het recursieve geval veranderen en u dichter bij het basisscenario brengen. Dit argument moet in het basisscenario worden getest. In het vorige voorbeeld, omdat we er één aftrekken in het recursieve geval, testen we of het argument gelijk is aan nul in ons basisscenario.
Accentsconagua
vermenigvuldigen (2,4) zal terugkeren 8. Schrijf voor wat er bij elke stap gebeurt vermenigvuldigen (2,4).Terugkeren in een lijst is vergelijkbaar met het terugkeren op een nummer, behalve dat in plaats van het aantal bij elke stap te verminderen, we de lijst bij elke stap verlagen totdat we bij een lege lijst komen.
Overweeg de somfunctie die een lijst als invoer neemt en de som van alle elementen in de lijst retourneert. Dit is een implementatie voor de functiesom:
function sum (l) if (empty (l)) return 0; else return car (l) + sum (cdr (l));
De leeg functie retourneert true als de lijst geen elementen bevat. De auto functie retourneert het eerste element in de lijst. Bijvoorbeeld, auto ([1,2,3,4]) retourneert 1. Het cdr functie retourneert de lijst zonder het eerste element. Bijvoorbeeld, CDR ([1,2,3,4]) geeft [2,3,4] terug. Wat gebeurt er als we uitvoeren? sum ([1,2,3,4])?
som ([1,2,3,4]) 1 + som ([2,3,4]) 1 + (2 + som ([3,4])) 1 + (2 + (3 + som ([4 ]))) 1 + (2 + (3 + (4 + sum ([])))) 1 + (2 + (3 + (4 + 0))) 1 + (2 + (3 + 4)) 1 + (2 + 7) 1 + 9 10
Als u terugkeert in een lijst, controleer dan of deze leeg is. Anders doet u de recursieve stap in een beperkte versie van de lijst.
lengte (['a', 'b', 'c', 'd']) zou terug moeten keren 4. Schrijf op wat er bij elke stap gebeurt.In het laatste voorbeeld gaven we een nummer terug. Maar stel dat we een lijst wilden teruggeven. Dat zou betekenen dat we in plaats van een nummer aan onze recursieve stap toe te voegen, we een lijst moeten toevoegen. Overweeg de functie verwijderen, die een item en lijst als invoer neemt en de lijst retourneert met het item verwijderd. Alleen het eerste gevonden item wordt verwijderd.
functie remove (item, l) if (empty (l)) return []; else if (eq (auto (l), item)) return cdr (l); else return cons (auto (l), remove (item, cdr (l))); remove ('c', ['a', 'b', 'c', 'd']) // ['a', 'b', 'd']Hier de eq function geeft true als beide inputs hetzelfde zijn. De cons functie neemt een element en een lijst als inputs en retourneert een nieuwe lijst met het element toegevoegd aan het begin ervan.
We zullen controleren of het eerste item in de lijst gelijk is aan het item dat we willen verwijderen. Als dit het geval is, verwijdert u het eerste element uit de lijst en retourneert u de nieuwe lijst. Als het eerste item niet gelijk is aan het item dat we willen verwijderen, nemen we het eerste element in de lijst en voegen we het toe aan de recursieve stap. De recursieve stap bevat de lijst met het eerste element verwijderd.
We zullen elementen blijven verwijderen totdat we onze basiscase bereiken, wat een lege lijst is. Een lege lijst betekent dat we alle items in onze lijst hebben doorlopen. Wat doet remove ('c', ['a', 'b', 'c', 'd']) do?
remove ('c', ['a', 'b', 'c', 'd']) cons ('a', remove ('c', ['b', 'c', 'd']) ) cons ('a', cons ('b', remove ('c', ['c', 'd']))) cons ('a', cons ('b', ['d']) tegens ('a', ['b', 'd']) ['a', 'b', 'd']In een situatie waarin we een lijst moeten samenstellen, nemen we het eerste element en voegen we het toe aan het recursieve deel van onze lijst.
remove ('c', ['a', 'b', 'c', 'd', 'c'] retourneert ['a', 'b', 'd']. Schrijf wat er gebeurt, stap voor stap.Er zijn drie delen aan een recursieve functie. De eerste is het basisscenario, wat de afsluitende voorwaarde is. De tweede is de stap om ons dichter bij onze basiscase te brengen. De derde is de recursieve stap, waarbij de functie zichzelf aanroept met de verminderde invoer.
Recursie is als iteratie. Elke functie die u recursief kunt definiëren, kan ook worden gedefinieerd met behulp van loops. Andere zaken die u in overweging moet nemen bij het gebruik van recursie, zijn terugkomend op geneste lijsten en het optimaliseren van uw recursieve oproepen.
Een geweldige bron om te blijven leren over recursie is het boek The Little Schemer. Het leert je recursief te denken met behulp van een vraag- en antwoordformat.
