I edb-programmering , rekursion opstår, når en funktion eller procedure - med andre ord , en sekvens af instruktioner til at udføre en bestemt funktion - kalder sig , enten direkte eller indirekte ? . Den funktion eller fremgangsmåde modificerer værdien af parameteren ( r) overføres til det første gang den kaldes , og kalder sig selv med den nye værdi (er ) . Fakulteterne
klassisk eksempel på rekursion indebærer computing fakulteterne . Et fakultet er produktet af en given positiv helt tal ganget med alle mindre hele tal . Fakultet af 5 er 5 * 4 * 3 * 2 * 1 , fakultet af 4 er 4 * 3 * 2 * 1 og så videre . Fakultet af et vilkårligt antal er lig med det tal ganget med fakultet antallet umiddelbart nedenfor . Med andre ord , er factorial ( 5) den samme som 5 * factorial ( 4 ) , factorial ( 4) er den samme som 4 * factorial ( 3 ) og så videre , så en simpel faktor funktion kan skrives som :
int factorial ( int n ) {return n * factorial (n - 1 );}
Base Case
problemet med denne simple funktion , dog er, at det ikke har nogen base case , eller betingelse for at fortælle det når at stoppe . Som det står , ville funktionen fortsætte med at kalde sig , når n nåede nul og videre ind i negative tal , returnere meningsløse fakulteterne . I virkeligheden skal en faktor , der kan stoppe , når n = 1 , så en reel faktor funktion kan skrives som :
int factorial ( int n ) { if ( n == 1 ) { tilbagevenden 1; } else {return n * factorial (n - 1 );}}
engelsk , funktionen undersøger antallet videre til det som en parameter , og hvis antallet er 1, returnerer 1 . Ellers returnerer funktionen tal ganget med fakultet af antallet minus én.
Program Stack
Alle rekursive programmer skal have en bund point , eller base sag, hvor operationen er så trivielt , at et svar kan returneres direkte. Rekursion virker ved at tilføje , eller skubbe , og fjerne eller popping , enkeltbilleder til og fra en datastruktur kendt som et program stak. Der er kun en begrænset mængde plads på programmet stakken , så uden en base tilfælde ville en rekursiv program blot fortsætter med at køre, indtil stakken overløb .
Pros & Cons
< br >
Recursion er svært at forstå , fordi det ikke er intuitiv og kan synes ved første øjekast at inddrage cirkulær eller falsk logik. Ifølge IBM er rekursion sjældent brugt af programmører i tvingende programmeringssprog - hvilket ikke angiver en eksplicit sekvens af trin for at udføre - fordi de tror det er langsom og affald plads. Men hvis den gennemføres korrekt , rekursion er en kraftfuld programmering teknik , der kan strømline nogle programmerings opgaver.