Recursie is een krachtig concept op het gebied van de informatica , maar het kan moeilijk zijn voor nieuwelingen te begrijpen . Recursie is een functie of methode herhaaldelijk roepen zich in een andere context tot een "basis " context wordt bereikt en geretourneerd . Met andere woorden , een probleem , het programma recontexualizes als een enigszins ander probleem . Bij de uitvoering van een recursieve algoritme , altijd rekening met de meest eenvoudige vorm van het probleem en stellen dit vereenvoudigde voorbeeld als een ' base case , " welke versies van het probleem alle andere zullen verwijzen . Instructies
1 Definieer header van de functie - naam van de functie en de inputs . Bijvoorbeeld, zou een functie die een bepaald Fibonacci getal komt er als volgt uit : fib
( int n ) { }
Hier , de functie berekent de " n " Fibonacci getal in de rij . kopen van 2 Noteer hoe de functie wordt generiek worden genoemd . Bijvoorbeeld , wanneer je fib ( ) bellen , zult u een integer gebruiken als argument en noteer het getal dat het berekent :
int result = fib ( x ) ;
3 Definieer de " base case" van uw recursie probleem . Er kunnen meerdere basisstations gevallen . Zoals de Fibonacci-reeks vereist twee nummers , zult u twee base gevallen nodig om zijn oplossing te implementeren
if ( n == 0 ) return 0 ; . If ( n == 1 ) return 1 ;
< br > 4 Definieer de recursieve stap van uw recursie probleem als een kleinere , eenvoudigere versie van hetzelfde probleem , dat verwijst naar de aanroeping voorbeeld uit stap 2 . In ons voorbeeld , de Fibonacci-reeks is een wiskundige reeks waarbij elk nummer in de lijn is de som van de twee voorgaande getallen in de reeks. Het algoritme om een bepaalde Fibonacci getal vinden moet dus beroepen zich twee keer , een keer voor het vorige nummer en eenmaal voor het nummer voor het vorige nummer : int
result1 = fib ( n - 1 ) ; int resultaat2 = fib ( n - 2 ) ;
terugkeer resultaat1 + resultaat2 ;
5 Zet de functie samen , bijvoorbeeld : fib
( int n ) { if ( n == 0 ) return 0 ; //base case 1else if ( n == 1 ) return 1 ; //base case 2
else { //recursieve stepint result1 = fib ( n - 1 ) ; int resultaat2 = fib ( n - 2 ) ;
terugkeer resultaat1 + resultaat2 ; } }
de structuur van de " base case " en " recursieve stap " zal hetzelfde zijn voor alle recursieve functies , hoewel er meerdere base gevallen en lange recursieve stappen kunnen zijn .
|
