Share
Noen problemer løses mer naturlig ved hjelp av rekursjon. For eksempel har en sekvens som Fibonacci-sekvensen en rekursiv definisjon. Hvert tall i sekvensen er summen av de to foregående tallene i sekvensen. Problemer som krever at du bygger eller traverser en treaktig datastruktur, kan også løses med rekursjon. Tren deg selv til å tenke rekursivt, vil gi deg en kraftig ferdighet til å angripe slike problemer.
I denne veiledningen vil jeg gå gjennom flere rekursive funksjoner trinn for trinn for å se hvordan de fungerer og vise teknikker du kan bruke til systematisk å definere rekursive funksjoner.
En rekursivt definert funksjon er en funksjon som er definert i form av en enklere versjon av seg selv. Dette er et forenklet eksempel:
funksjon doA (n) ... doA (n-1);
For å forstå hvordan rekursjon fungerer konseptuelt, vil vi se på et eksempel som ikke har noe å gjøre med kode. Tenk deg at du er ansvarlig for å svare på telefonsamtaler på jobben. Siden dette er et travelt selskap, har telefonen flere telefonlinjer, slik at du kan jonglere flere samtaler samtidig. Hver telefonlinje er en knapp på mottakeren, og når det kommer et innkommende anrop, blinker knappen. I dag, når du kommer til jobb og slår på telefonen, er det fire linjer som blinker på en gang. Så du kommer til å svare på alle anropene.
Du plukker opp linje ett og forteller dem 'vær så snill'. Så plukker du opp linje to og legger dem på vent. Deretter plukker du opp linje tre og legger dem på vent. Til slutt svarer den fjerde linjen du og snakker med den som ringer. Når du er ferdig med den fjerde ringeren, henger du opp og henter det tredje anropet. Når du er ferdig med det tredje anropet, henger du opp og henter den andre anropet. Når du er ferdig med det andre anropet, henger du opp og henter den første samtale. Når du er ferdig med samtalen, kan du endelig sette telefonen ned.
Hver telefonsamtale i dette eksemplet er som et rekursivt anrop i en funksjon. Når du ringer, blir den satt på anropsstakken (i kodespråket). Hvis du ikke kan fullføre en samtale med en gang, setter du anropet på vent. Hvis du har et funksjonsanrop som ikke kan evalueres umiddelbart, forblir det på anropsstakken. Når du er i stand til å svare på et anrop, blir det plukket opp. Når koden din er i stand til å evaluere et funksjonsanrop, stikker det fra stakken. Hold denne analogien i tankene når du ser over de følgende kodeeksemplene.
Alle rekursive funksjoner trenger en basis sak, så de vil avslutte. Men bare å legge til en basissak til vår funksjon, forhindrer ikke det i å løpe uendelig. Funksjonen må ha et skritt for å bringe oss nærmere basissaken. Sist er det rekursive trinnet. I det rekursive trinnet blir problemet redusert til en mindre versjon av problemet.
Anta at du har en funksjon som vil summere tallene fra 1 til n. For eksempel, hvis n = 4, vil det summe 1 + 2 + 3 + 4.
Først bestemmer vi basisscenariet. Å finne basisscenariet kan også tenkes som å finne saken der problemet kan løses uten rekursjon. I dette tilfellet er det når n er lik null. Null har ingen deler, så vår rekursjon kan stoppe når vi når 0.
Ved hvert trinn trekker du en fra det nåværende nummeret. Hva er rekursiv sak? Den rekursive saken er funksjonssummen kalt med det reduserte nummeret.
funksjon sum (num) if (num === 0) return 0; ellers return num + sum (- num) sum (4); // 10
Dette er hva som skjer i hvert trinn:
Dette er en annen måte å se hvordan funksjonen behandler hvert anrop:
sum (4) 4 + sum (3) 4 + (3 + sum (2)) 4 + (3 + (2 + sum (1))) 4 + (3 + (2 + ) 4 + (3 + (2 + (1 + 0))) 4 + (3 + (2 + 1)) 4 + (3 + 3) 4 + 6 10
Argumentet bør endres i rekursiv sak og bringe deg nærmere basissettet. Dette argumentet bør testes i basissettet. I det forrige eksempelet, fordi vi trekker en i rekursiv saken, tester vi om argumentet er null i vårt grunnleggende tilfelle.
Accentsconagua
multiplisere (2,4) vil returnere 8. Skriv hva som skjer i hvert trinn for multiplisere (2,4).Gjentagende på en liste ligner gjentagende på et tall, bortsett fra at i stedet for å redusere nummeret ved hvert trinn, reduserer vi listen ved hvert trinn til vi kommer til en tom liste.
Vurder summen funksjonen som tar en liste som input og returnerer summen av alle elementene i listen. Dette er en implementering for funksjonsbeløpet:
funksjonssummen (l) hvis (tom (l)) return 0; ellers returbil (l) + sum (cdr (l));
De tømme Funksjonen returnerer sann hvis listen ikke har noen elementer. De bil funksjonen returnerer det første elementet i listen. For eksempel, bil ([1,2,3,4]) returnerer 1. Den cdr funksjonen returnerer listen uten det første elementet. For eksempel, CDR ([1,2,3,4]) returnerer [2,3,4]. Hva skjer når vi utfører sum ([1,2,3,4])?
sum ([1,2,3,4]) 1 + sum ([2,3,4]) 1 + (2 + sum ([3,4])) 1 + (2 + (3 + sum ([4 ])) 1 + (2 + (3 + (4 + sum ([]))) 1 + (2 + (3 + (4 + 0)) 1 + (2 + (3 + 4)) 1 + (2 + 7) 1 + 9 10
Når du er tilbake på en liste, kontroller du om den er tom. Ellers gjør det rekursive trinnet på en redusert versjon av listen.
lengde (['a', 'b', 'c', 'd')) skal returnere 4. Skriv hva som skjer i hvert trinn.I det siste eksemplet returnerte vi et nummer. Men antar at vi ønsket å returnere en liste. Det ville bety at vi i stedet for å legge til et nummer til vårt rekursive trinn, måtte legge til en liste. Vurder funksjonen fjerne, som tar en vare og liste som input og returnerer listen med elementet fjernet. Bare det første funnet elementet blir fjernet.
funksjon fjerner (element, l) hvis (tomt (l)) return []; annet hvis (eq (bil (l), element)) return cdr (l); ellers retur ulemper (bil (l), fjern (element, cdr (l))); fjern ('c', ['a', 'b', 'c', 'd']) // ['a', 'b', 'd']Her, den ekv Funksjonen returnerer sann hvis begge inngangene er de samme. De ulemper funksjonen tar et element og en liste som innganger og returnerer en ny liste med elementet lagt til i begynnelsen av det.
Vi vil sjekke om det første elementet i listen er lik det elementet vi vil fjerne. Hvis det er, fjern det første elementet fra listen og returner den nye listen. Hvis det første elementet ikke er lik det elementet vi vil fjerne, tar vi det første elementet i listen og legger det til rekursivt trinn. Det rekursive trinnet vil inneholde listen med det første elementet fjernet.
Vi vil fortsette å fjerne elementer før vi kommer til vårt grunnleggende tilfelle, som er en tom liste. En tom liste betyr at vi har krysset alle elementene i vår liste. Hva gjør fjern ('c', ['a', 'b', 'c', 'd']) gjøre?
fjern ('c', ['a', 'b', 'c', 'd']) cons ('a', fjern ('c', ['b', 'c', 'd']) ) ulemper ('a', cons ('b', remove ('c', ['c', 'd'])) cons ('a', ['b', 'd']) ['a', 'b', 'd']I en situasjon når vi trenger å bygge en liste, tar vi det første elementet og legger det til den rekursive delen av listen.
fjern ('c', ['a', 'b', 'c', 'd', 'c'] returnerer ['a', 'b', 'd']. Skriv hva som skjer trinnvis.Det er tre deler til en rekursiv funksjon. Den første er basissaken, som er avslutningsbetingelsen. Den andre er trinnet for å komme oss nærmere til vårt grunnleggende tilfelle. Den tredje er det rekursive trinnet, hvor funksjonen kaller seg med den reduserte inngangen.
Rekursjon er som iterasjon. En hvilken som helst funksjon som du kan definere rekursivt, kan også defineres ved hjelp av løkker. Andre ting du bør vurdere når du bruker rekursjon, gjentas på nestede lister og optimaliserer dine rekursive samtaler.
En stor ressurs for å fortsette å lære om rekursjon er boken The Little Schemer. Det lærer deg hvordan du tenker rekursivt ved hjelp av et spørsmål og svarformat.
