Sådan fungerer rekursion - forklaret med flowcharts og en video

"For at forstå rekursion skal man først forstå rekursion."

Rekursion kan være svært at forstå - især for nye programmører. I sin enkleste form er en rekursiv funktion en, der kalder sig selv. Lad mig prøve at forklare med et eksempel.

Forestil dig at du går for at åbne døren til soveværelset, og den er låst. Din treårige søn kommer ind fra hjørnet og fortæller dig, at han gemte den eneste nøgle i en kasse. (”Ligesom ham,” tænker du.) Du er forsinket til arbejde, og du skal virkelig komme ind i lokalet for at få din skjorte.

Du åbner kun kassen for at finde ... flere kasser. Æsker inde i æsker. Og du ved ikke, hvilken der har nøglen! Du er nødt til at få den trøje snart, så du er nødt til at tænke på en god algoritme for at finde den nøgle.

Der er to hovedtilgange til at oprette en algoritme for dette problem: iterativ og rekursiv. Her er begge tilgange som rutediagrammer:

Hvilken tilgang virker lettere for dig?

Den første tilgang bruger en while-loop. Mens bunken ikke er tom, skal du gribe en kasse og se igennem den. Her er nogle JavaScript-inspirerede pseudokoder, der viser, hvad der sker. (Pseudokode er skrevet som kode, men menes at være mere som menneskelig tale.)

function look_for_key(main_box) { let pile = main_box.make_a_pile_to_look_through(); while (pile is not empty) { box = pile.grab_a_box(); for (item in box) { if (item.is_a_box()) { pile.append(item) } else if (item.is_a_key()) { console.log("found the key!") } } }}

Den anden måde bruger rekursion. Husk, rekursion er, hvor en funktion kalder sig selv. Her er anden vej i pseudokode.

function look_for_key(box) { for (item in box) { if (item.is_a_box()) { look_for_key(item); } else if (item.is_a_key()) { console.log("found the key!") } } }

Begge tilgange udfører den samme ting. Hovedformålet med at bruge den rekursive tilgang er, at når du først forstår det, kan det være tydeligere at læse. Der er faktisk ingen præstationsfordel ved at bruge rekursion. Den iterative tilgang med sløjfer kan undertiden være hurtigere. Men især foretrækkes enkeltheden ved rekursion undertiden.

Da mange algoritmer bruger rekursion, er det også vigtigt at forstå, hvordan det fungerer. Hvis rekursion stadig ikke synes at være enkel for dig, skal du ikke bekymre dig: Jeg vil gennemgå et par flere eksempler.

Basissag og rekursiv sag

Noget du skal passe på, når du skriver en rekursiv funktion, er en uendelig løkke. Dette er når funktionen fortsætter med at kalde sig selv ... og aldrig holder op med at ringe selv!

For eksempel vil du muligvis skrive en nedtællingsfunktion. Du kan skrive det rekursivt i JavaScript sådan:

// WARNING: This function contains an infinite loop! function countdown(i) { console.log(i) countdown(i - 1)} countdown(5); // This is the initial call to the function.

Denne funktion vil fortsætte med at tælle for evigt. Hvis du ved et uheld kører kode med en uendelig løkke, kan du trykke på "Ctrl-C" for at dræbe dit script. (Eller hvis du nogle gange bruger CodePen som mig, skal du tilføje "? Turn_off_js = true" i slutningen af ​​URL'en.)

En rekursiv funktion skal altid sige, hvornår man skal stoppe med at gentage sig selv. Der skal altid være to dele til en rekursiv funktion: den rekursive sag og basissagen. Det rekursive tilfælde er, når funktionen kalder sig selv. Basissagen er, når funktionen holder op med at ringe til sig selv. Dette forhindrer uendelige sløjfer.

Her er nedtællingsfunktionen igen med en basissag:

function countdown(i) { console.log(i) if (i <= 1) { // base case return; } else { // recursive case countdown(i - 1); } } countdown(5); // This is the initial call to the function.

Det er måske ikke tydeligt, hvad der sker i denne funktion. Jeg gennemgår, hvad der sker, når du kalder nedtællingsfunktionen, der går i "5".

Vi starter med at udskrive nummer 5 ved hjælp af console.log. Da fem ikke er mindre end eller lig med nul, går vi til den anden erklæring. Der kalder vi nedtællingsfunktionen igen med tallet fire (5–1 = 4?).

Vi logger tallet 4. Igen ier det ikke mindre end eller lig med nul, så vi går til den anden erklæring og kalder nedtælling med 3. Dette fortsætter indtilier lig med nul. Når det sker, skal du logge vi tallet nul og derefter ier mindre end eller lig med nul. Endelig kommer vi til returopgørelsen og springer ud af funktionen.

Opkaldsstakken

Rekursive funktioner bruger noget, der kaldes "opkaldstakken". Når et program kalder en funktion, går denne funktion oven på opkaldstakken. Dette ligner en stak bøger. Du tilføjer ting en ad gangen. Så når du er klar til at tage noget af, tager du altid det øverste element af.

Jeg viser dig opkaldsstakken i aktion med factorialfunktionen. factorial(5)er skrevet som 5! og det er defineret således: 5! = 5 * 4 * 3 * 2 * 1. Her er en rekursiv funktion til beregning af et tals faktor:

function fact(x) { if (x == 1) { return 1; } else { return x * fact(x-1); } }

Lad os nu se, hvad der sker, hvis du ringer til fact(3). Illustrationen nedenfor viser, hvordan stakken ændres, linje for linje. Det øverste felt i stakken fortæller dig, hvilket opkald factdu befinder dig i øjeblikket.

Læg mærke til, hvordan hvert opkald til facthar sin egen kopi af x. Dette er meget vigtigt for at få rekursionsarbejde til at fungere. Du har ikke adgang til en kopi af en anden funktion x.

Fandt du nøglen endnu?

Lad os kort gå tilbage til det oprindelige eksempel om at kigge efter en nøgle i indlejrede felter. Husk, den første metode var iterativ ved hjælp af sløjfer. Med denne metode laver du en bunke kasser til at søge igennem, så du altid ved, hvilke kasser du stadig har brug for at søge på.

Men der er ingen bunke i den rekursive tilgang. Hvordan ved din algoritme, hvilke bokse du stadig skal se? “Bunken med kasser” gemmes på stakken. Dette er en stak med halvt udførte funktionsopkald, hver med sin egen halvkomplette liste over felter, du skal se igennem. Stakken holder styr på bunken med kasser til dig!

Og takket være rekursion kan du endelig finde nøglen og få din skjorte!

Du kan også se denne 5-minutters video, jeg lavede om rekursion. Det bør styrke disse rekursionskoncepter.

Konklusion

Jeg håber, at denne artikel gav dig mere klarhed om rekursion i programmering. Denne artikel er baseret på en lektion i mit nye videokursus fra Manning Publications kaldet Algorithms in Motion. Kurset (og også denne artikel) er baseret på den fantastiske bog Grokking Algorithms af Adit Bhargava. Det er ham, der tegner alle de sjove illustrationer i denne artikel.

Hvis du lærer bedst gennem bøger, skal du hente bogen! Hvis du lærer bedst gennem videoer, kan du overveje at købe mit kursus.

Få 39% rabat på mit kursus ved at bruge koden ' 39carnes '!

Og endelig, for virkelig at forstå rekursion, skal du læse denne artikel igen. ?