Recursion er et stærkt koncept inden for computer science , men det kan være svært for nybegyndere at forstå. Recursion indebærer en funktion eller metode gentagne påberåber sig i en anden sammenhæng , indtil en "base " kontekst er nået og returneres. Med andre ord , for at løse et problem programmet recontexualizes det som et lidt anderledes problem . Ved gennemførelsen af en rekursiv algoritme , altid overveje den mest simple form af problemet og etablere denne forenklede eksempel som en " base case ", hvor alle andre versioner af problemet vil referere . Instruktioner
1
Definer en funktion header - funktionens navn og dens input . For eksempel kan en funktion, der finder en bestemt Fibonacci-tal se ud som følger : Hej
fib ( int n ) { }
Her funktionen beregner " n'te " Fibonacci-tal i sekvensen .
2
Skriv ned, hvordan funktionen bliver kaldt generisk . For eksempel, når du kalder fib ( ), vil du bruge en heltal som argument og registrere heltal , at det beregner : Hej
int resultat = fib (x ),
3
Definer "base case" på din rekursion problem. Der kan være flere baser sager. Da Fibonacci sekvensen kræver to numre , skal du bruge to base sager at gennemføre sin løsning
if ( n == 0 ) return 0 ; . If ( n == 1 ) tilbagevenden 1;
< br > 4.
Definer rekursive trin i din rekursion problem som en mindre , enklere udgave af det samme problem, der refererer til påkaldelse eksempel fra trin 2 . I vores eksempel er Fibonacci en matematisk sekvens, hvor hvert nummer i rækken er summen af de to foregående tal i sekvensen . Algoritmen til at finde en bestemt Fibonacci-tal skal derfor påberåbe sig to gange , én gang for det tidligere antal og en gang for antallet inden den tidligere nummer : Hej
int resultatet1 = fib (n-1 ), int result2 = fib ( n -2)
afkast resultatet1 + result2 ,
5
Sæt funktionen sammen , fx : Hej
fib ( int n ) {if (n == 0) return 0 ; //base case 1else if ( n == 1 ) return 1 //base case 2
else { //rekursiv stepint resultatet1 = fib (n-1 ), int result2 = fib (n -2)
afkast resultatet1 + result2 ;}
}
struktur "base case" og " rekursiv skridt " vil være den samme for alle rekursive funktioner , selv om der kan være flere baser sager og lange rekursive trin.