rekursion kan vara en användbar teknik för programmerare . Rekursiva funktioner , som ibland kallas " metoder " i språk som Java , är funktioner som kallar sig . Det finns vissa situationer där rekursiva funktioner är särskilt lämpliga . Däremot kan det vara svårt att korrekt genomföra en rekursiv funktion , så de bör endast användas där så är lämpligt . Rekursiva funktioner är ofta användbara när man hanterar datastrukturer och matematiska aktiviteter . Sortering
När modellprogram uppgifter , antingen internt eller importeras från en källa såsom en databas , de ofta behöver sortera det . Vissa datastrukturer inte beställts , vilket innebär att elementen inte är ordnade i nummerordning . Till exempel kan ett program innehålla en array med textsträngar inuti. För att sortera arrayen så att textsträngar är ordnade i stigande ordning alfabetiskt , kan programmet behöva använda en algoritm . Merge sort är ett exempel på en rekursiv metod för denna process. Merge sortera fungerar genom att kontinuerligt dela arrayen i två , sortering varje halva innan sammanslagningen dem tillbaka till en.
Söka
När program lagrar data i datastrukturer , de ofta måste hitta vissa delar med sökalgoritmer , som kan dra nytta av rekursion . Till exempel, om en matris lagrar värdena i alfabetisk ordning , kan programmet använda rekursion för att räkna ut vilken position ett visst element är på . Binary Search innebär programmet kontinuerligt kontrollera ett element halvvägs igenom arrayen . Om elementet matchar ena programmet är ute efter , kan det sluta . Om det inte är det element i fråga, kan algoritmen kontrollera om det är större eller mindre än sökandet elementet. Om den är större , kan algoritmen eliminera den övre hälften av strukturen utanför det aktuella elementet , eftersom sökningen elementet måste vara i den nedre halvan . Denna process fortsätter tills elementet ligger .
Data Structures
När beslut fattas om algoritmer , bör programmerare be om en iterativ funktion som inte är rekursiv kunde lösa uppgiften samt en rekursiv en . Till exempel , i vissa datastrukturer , kommer ett program att behöva söka igenom på ett linjärt sätt tills den lokaliserar en sökning objekt . I detta fall finns det inget annat alternativ än att iterera genom strukturen . Rekursiva algoritmer förenkla uppgiften med varje iteration , kontrollera om slutpunkten har anlänt , och sedan anropa funktionen igen om det inte har . För att visa likheterna mellan rekursion och iteration , visar följande exempel Java metod en rekursiv metod kontur : public void processNumber ( int myNum ) {if ( myNum > 100 ) avkastning , annars processNumber ( myNum * 5 ) ; }
Ett alternativ iterativ implementering av detta skulle vara följande : . int Anum = 3 , medan ( Anum < 100 ) { Anum * = 5 ; }
i detta fall iterativa versionen är enklare
matematiska uppgifter
Vissa matematiska bearbetning uppgifter är särskilt väl lämpade för rekursiva funktioner . Fibonacci sekvenser visar rekursiv bearbetning . Varje siffra i en Fibonacci-följd är summan av de två föregående. Följande exempel Java-kod visar en funktion för att hitta ett Fibonacci nummer : public int getFibonacci ( int fNum ) {if ( fNum < = 1 ) återvändande fNum , annars avkastning getFibonacci ( fNum - 1 ) + getFibonacci ( fNum - 2 ) ; }
metoden returnerar numret i Fibonacci -sekvensen vid den position som anges av ett heltal parameter när koden kallar det , enligt följande : getFibonacci ( 8 ) ,
Detta skulle återvända åttonde numret . ( Se referenser 3 , 4 , 5 ) Addera
