Hvordan løse Rekursjon

Rekursjon er et kraftig konsept innen informatikk, men det kan være vanskelig for nybegynnere å forstå. Rekursjon innebærer en funksjon eller en metode gjentatte ganger å påkalle seg i en annen sammenheng til en "base" sammenheng er nådd, og returnert. Med andre ord, for å løse et problem, vil programmet recontexualizes det som et litt annerledes problem. Ved implementering av en rekursiv algoritme, alltid vurdere enkleste form av problemet og etablere denne forenklet eksempel som en "base case", som alle andre versjoner av problemet vil referere til.

Bruksanvisning

1 Definer en funksjon overskriften - funksjonens navn og innganger. For eksempel, en funksjon som finner en bestemt Fibonacci-tall kan se ut som følger:

fib (int n) {}

Her, beregner funksjonen "n'te" Fibonacci nummer i sekvensen.

2 Skriv ned hvordan funksjonen skal kalles generisk. For eksempel, når du ringer fib (), vil du bruke en heltall som argument og registrere heltall som den beregner:

int resultat = fib (x);

3 Definer "base case" av rekursjon problem. Det kan være flere base tilfeller. Som Fibonacci-sekvensen krever to tall, trenger du to grunn tilfeller å implementere sin løsning.

if (n == 0) return 0;
if (n == 1) avkastning 1;

4 Definer rekursive trinn av rekursjon problem som en mindre, enklere versjon av det samme problemet, refererer påkalling eksempel fra trinn 2. I vårt eksempel er Fibonacci-sekvensen en matematisk sekvens der hvert nummer i rekken er summen av den forrige to tall i sekvensen. Algoritmen for å finne en bestemt Fibonacci-tall må derfor påberope seg to ganger, en gang for forrige nummer, og en gang for nummeret før forrige nummer:

int result1 = fib (n-1);
int result2 = fib (n-2);

tilbake result1 + result2;

5 Sett funksjonen sammen, for eksempel:

fib (int n) {
if (n == 0) return 0; // Base case 1
else if (n == 1) avkastning 1; // Base case 2

else {// rekursive trinn
int result1 = fib (n-1);
int result2 = fib (n-2);

tilbake result1 + result2;
}

}

Strukturen av "base case" og "rekursiv trinn" vil være den samme for alle rekursive funksjoner, selv om det kan være flere base tilfeller og lange rekursive trinn.

Hint

• For å hjelpe deg å visualisere en rekursiv løsning, gå gjennom programmets innganger og avkastning ved hjelp av en prøve problem.
• Uansett hvordan du implementere funksjonen, må den alltid tilbake sin base case på et eller annet tidspunkt i løpet av programmets gjennomføring. Ellers vil funksjonen aldri slutte å kalle seg selv!