Recursion kan være en nyttig teknik til programmører. Rekursive funktioner , også kaldet "metoder " i sprog som Java , er funktioner , der kalder sig selv. Der er visse situationer, hvor rekursive funktioner er særligt egnede . Dog kan det være svært at korrekt gennemføre en rekursiv funktion , så de bør kun anvendes, hvor det er relevant. Rekursive funktioner er ofte nyttige, når der beskæftiger sig med datastrukturer og matematiske aktiviteter . Sortering
Når programmer modeldata , enten internt eller importeres fra en kilde , såsom en database , de ofte har brug for at sortere det . Nogle datastrukturer ikke bestilt, hvilket betyder, at elementerne er ikke arrangeret i rækkefølge . For eksempel kunne et program indeholde et array med tekststrenge inde i det . At sortere array , så tekststrenge er arrangeret i stigende rækkefølge alfabetisk, kan programmet bruge en algoritme. Fusionere slags er et eksempel på en rekursiv metode til denne proces . Flet sortere virker ved løbende at dividere matrix i to, sortering hver halvdel , før fusionerende dem tilbage i én.
Søgning
Når programmer gemme data i datastrukturer , de ofte brug for at finde bestemte elementer ved hjælp af søge algoritmer, der kan komme i rekursion . For eksempel, hvis en matrix er lagring værdier i alfabetisk rækkefølge kan programmet bruge rekursion til at regne ud, hvad position et vist element er . Binær søgning indebærer programmet løbende kontrollere et element midtvejs gennem matrixen . Hvis elementet matcher det program er på udkig efter , kan det stoppe. Hvis det ikke er det pågældende element , kan algoritmen kontrollere, om det er større eller mindre end den søgeelementet . Hvis det er større , kan algoritmen fjerne den øverste halvdel af strukturen ud over det aktuelle element , som søgningen elementet skal være i den nederste halvdel . Denne proces fortsætter, indtil elementet er placeret.
Datastrukturer
Når der træffes beslutning om algoritmer , bør programmører spørge, om en iterativ funktion, der ikke er rekursive kunne løse opgaven samt en rekursiv én . For eksempel, i visse datastrukturer vil et program nødt til at søge igennem på en lineær måde , indtil det lokaliserer en søgning item . I dette tilfælde er der intet alternativ til gentage gennem strukturen. Rekursive algoritmer forenkle opgaven med hver iteration , kontrol for at se , om slutpunktet er ankommet , og derefter kalde funktionen igen, hvis den ikke har . For at demonstrere lighederne mellem rekursion og iteration følgende prøve Java metode viser en rekursiv metode skitse : public void processNumber ( int myNum ) { if ( myNum > 100) tilbagevenden; ellers processNumber ( myNum * 5 );}
< p > Et alternativ iterativ implementering af dette ville være som følger: . int Anum = 3 , mens ( Anum < 100) { Anum * = 5 ;}
i dette tilfælde den iterative versionen er enklere
< br >
matematiske opgaver
Nogle matematiske behandling opgaver er særligt velegnede til rekursive funktioner . Fibonacci -sekvenser demonstrere rekursive forarbejdning. Hvert nummer i en Fibonacci er summen af de to foregående. Følgende eksempel Java-kode demonstrerer en funktion til at finde en Fibonacci-tal : public int getFibonacci ( int fNum ) { if ( fNum < = 1 ) return fNum , ellers retur getFibonacci ( fNum -1) + getFibonacci ( fNum -2) ;} < br >
metode returnerer nummeret i Fibonacci på den position indikeret ved et heltal parameter, når koden kalder det , som følger: getFibonacci (8);
Dette ville returnere den ottende nummer. (Se Referencer 3 , 4, 5 )