rekursion är ett kraftfullt koncept inom datavetenskap , men det kan vara svårt för nybörjare att förstå . Rekursion omfattar en funktion eller metod som upprepade gånger åberopar sig i ett annat sammanhang tills en " bas " kontext nås och returneras . Med andra ord , för att lösa ett problem , recontexualizes programmet det som ett något annorlunda problem . Vid genomförandet av en rekursiv algoritm , alltid överväga den enklaste formen av problemet och införa detta förenklade exempel som en " base case ", som alla andra versioner av problemet kommer att referera till . Instruktioner
1
Definiera en funktion sidhuvud - funktionens namn och dess ingångar . Till exempel kan en funktion som hittar ett visst Fibonacci nummer se ut enligt följande :
fib ( int n ) { }
Här beräknar funktionen " femtioelfte " Fibonacci nummer i sekvensen .
2
Skriv ner hur funktionen kommer att kallas generiskt . Till exempel när du ringer fib ( ) , kommer du att använda ett heltal som argument och registrera heltal som den beräknar :
int resultat = fib ( x ) ,
3
Definiera " base case " i din rekursion problem . Det kan finnas flera basfallen . Som Fibonacci sekvensen kräver två siffror , behöver du två basfallen att implementera sin lösning
if ( n == 0 ) return 0; . If ( n == 1 ) return 1 ;
4
Definiera rekursiva steget i din rekursion problem som en mindre , enklare version av samma problem , referera till åkallan exempel från steg 2 . I vårt exempel , är Fibonacci -sekvensen en matematisk sekvens där varje nummer i raden är summan av de två föregående nummer i sekvensen . Algoritmen för att hitta ett visst Fibonacci nummer måste därför åberopa sig två gånger , en gång för det föregående numret och en gång för numret innan det föregående numret :
int resultat1 = fib ( n- 1 ) ; int result2 = fib ( n- 2 );
retur resultat1 + result2 ;
5
Sätt funktionen sammanfogas t.ex. :
fib ( int n ) { if ( n == 0 ) return 0; //base case 1else if ( n == 1 ) return 1 ; //base case 2 Review
else { //rekursiv stepint resultat1 = fib ( n- 1 ) ; int result2 = fib (n- 2 );
retur resultat1 + result2 ;}
}
strukturen för " basfallet " och " rekursiv steg" kommer att vara densamma för alla rekursiva funktioner , även om det kan finnas flera basfallen och långa rekursiva steg .
