In het programmeren van computers , recursie treedt op wanneer een functie of procedure - met andere woorden , een reeks instructies voor het uitvoeren van een bepaalde functie - noemt zichzelf , hetzij direct of indirect . De functie of procedure wijzigt de waarde van de parameter ( s ) die wordt doorgegeven het eerst genoemd en dringt zich de nieuwe waarde (n ) . Faculteiten
Het klassieke voorbeeld van recursie gaat informatica faculteiten . Een faculteit is het product van elk positief geheel getal vermenigvuldigd met alle lagere gehele getallen . De faculteit van 5 is 5 * 4 * 3 * 2 * 1 , de faculteit van 4 is 4 * 3 * 2 * 1 enzovoorts . De faculteit van een getal is gelijk aan het aantal vermenigvuldigd met de faculteit van het nummer direct eronder . Met andere woorden , factorial ( 5 ) gelijk is aan 5 * factorial ( 4 ) , faculteit ( 4 ) is dezelfde als 4 * factorial ( 3 ) en dergelijke, zodat een eenvoudige faculteit-functie kan worden geschreven als :
int faculteit ( int n ) { return n * faculteit ( n - 1 ) ; }
Base Case
Het probleem met deze eenvoudige functie , echter , is dat het geen base case , of voorwaarde om het te vertellen wanneer te stoppen . Zoals het er nu , zou de functie zich blijven bellen als n nul bereikt en verder in negatieve getallen , terugkerende onzinnige faculteiten . In werkelijkheid , een faculteit-functie moet stoppen wanneer n = 1 , dus een echte faculteit-functie kan worden geschreven als : int
faculteit ( int n ) { if ( n == 1 ) { return 1 ; } else { return n * faculteit ( n - 1 ) ; } }
Engels , de functie bekijkt hoe doorgegeven als parameter en , als het getal 1 , geeft 1 . Anders retourneert de functie het aantal vermenigvuldigd met de faculteit van het aantal min een .
Programma Stack
Alle recursieve programma's moeten een onderste punt , of basis hebben geval , waar de operatie is zo triviaal dat een antwoord direct kunnen worden geretourneerd . Recursie werkt door het toevoegen of duwen en verwijderen of knallen , individuele frames en naar een gegevensstructuur bekend als programma stack . Er is maar een eindige hoeveelheid ruimte op het programma stack , dus , zonder een base case , een recursieve programma zou gewoon blijven draaien totdat de stapel overstroomde .
Pros & Cons
< br Recursion > is een moeilijk te begrijpen , want het is niet intuïtief en lijkt , op het eerste gezicht , om ronde of valse logica te betrekken . Volgens IBM , wordt recursie zelden gebruikt door programmeurs in imperatieve programmeertalen - die niet expliciet opeenvolging van stappen om te presteren wordt opgegeven - omdat ze denken dat het is traag en afvalstoffen ruimte . Echter , indien correct toegepast , recursie is een krachtige programmeertaal techniek die een beetje kan programmeren taken kunnen stroomlijnen .
|
