Rekursjon er en kraftig konsept innen informatikk , men det kan være vanskelig for nybegynnere å forstå. Rekursjon innebærer en funksjon eller metode gjentatte ganger påberope seg i en annen kontekst til en "base " kontekst er nådd og returnert. Med andre ord , for å løse et problem , recontexualizes programmet 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. Instruksjoner
en
Definer en funksjon header - funksjonens navn og dens innganger . For eksempel kan en funksjon som finner en bestemt Fibonacci-tall se slik ut:
løgn ( int n ) { }
Her beregner funksjonen " n-te " Fibonacci-tall i sekvensen .
2
Skriv ned hvordan funksjonen skal kalles generisk . For eksempel, når du kaller løgn ( ), vil du bruke ett heltall som argument og registrere heltall som det beregner : en
int resultat = fib ( x ) ;
3
Definer "base case" av rekursjon problem . Det kan være flere baser tilfeller. Som Fibonacci -sekvensen krever to tall, trenger du to basen tilfeller å gjennomføre sin løsning
if ( n == 0 ) return 0 ; . If ( n == 1 ) return 1;
4
Definer den rekursive trinn av rekursjon problem som en mindre, enklere versjon av det samme problemet , refererer påkalling eksempel fra trinn to . I vårt eksempel , er Fibonacci- sekvensen en matematisk sekvens der hvert tall i linjen er summen av de to foregående tallene i sekvensen. Algoritmen for å finne en bestemt Fibonacci-tall må derfor påberope seg to ganger , en gang i forrige nummer og en gang for nummeret før forrige nummer:
int result1 = fib ( n - 1 ) ; int result2 = fib ( n - 2 ) ;
retur result1 + result2 ;
5
Sett funksjonen sammen , f.eks : en
løgn ( int n ) { if ( n == 0 ) return 0 ; //base case 1else if ( n == 1 ) return 1; //base case 2
else { //rekursiv stepint result1 = fib ( n - 1 ) ; int result2 = løgn ( n - 2 ) ;
retur result1 + result2 ;}
}
strukturen i "base case" og " rekursiv steg" vil være den samme for alle rekursive funksjoner , selv om det kan være flere baser saker og lange rekursive trinn .
