I dataprogrammering, oppstår rekursjon når en funksjon eller prosedyre - med andre ord , en sekvens av instruksjoner for å utføre en bestemt funksjon - kaller seg , enten direkte eller indirekte ? . Funksjonen eller prosedyren endrer verdien av parameter ( e) sendes til det første gang det kalles og kaller seg selv med den nye verdien ( e). Fakultetene

klassisk eksempel på rekursjon innebærer databehandling fakultetene . En fakultet er produktet av et gitt positivt heltall multiplisert med alle mindre hele tall . Fakultetet av 5 er 5 * 4 * 3 * 2 * 1, er fakultetet av fire 4 * 3 * 2 * 1 og så videre . Fakultetet av et tall er lik det tallet multiplisert med fakultetet for nummeret umiddelbart under det. Med andre ord, er faktoriell ( 5) på samme måte som 5 * faktoriell (4) , faktoriell (4) er det samme som 4 * faktoriell (3) og så videre, slik at en enkel faktoriell funksjon kan skrives som:

int fakultet ( int n ) {return n * fakultet ( n - 1 ) ;}
Base sak

problemet med denne enkle funksjonen , derimot , er at den har ingen base tilfellet, eller tilstanden til å fortelle når den skal stoppe. Som det står, vil funksjonen fortsette å kalle seg når n nådd null og utover i negative tall , returnerer nonsens fakultetene . I virkeligheten trenger et fakultet funksjon å stoppe når n = 1 , så en ekte fakultet funksjon kan skrives som:

int fakultet ( int n ) { if ( n == 1 ) {return 1 ; } else {return n * fakultet ( n - 1 ); } }

på engelsk undersøker funksjon nummeret gått til det som en parameter og , hvis tallet er 1, returnerer ett . Ellers funksjonen returnerer antall multiplisert med fakultetet for antall minus én .
Program Stack

Alle rekursive programmer må ha et bunnpunkt , eller base tilfelle , hvor operasjonen er så ubetydelig at et svar kan returneres direkte. Rekursjon fungerer ved å legge til eller skyve, og fjerne eller popping, enkeltbilder til og fra en datastruktur som kalles et program stack. Det er bare en begrenset mengde plass på programmet stabelen , så, uten en base case , ville en rekursiv program bare fortsetter å kjøre inntil bunken fløt .
Pros & Cons

Rekursjon er en vanskelig å forstå fordi det ikke er intuitivt og kan virke ved første øyekast , å involvere sirkulær eller falsk logikk. Ifølge IBM er rekursjon sjelden brukes av programmerere i imperative programmeringsspråk - som ikke angir en eksplisitt sekvens av trinn for å utføre - fordi de tror det er treg og avfall plass . Men hvis implementert riktig , er rekursjon en kraftig programmering teknikk som kan effektivisere noen programmeringsoppgaver .