Rekursiivinen

Tietokoneohjelmoinnissa termi rekursiivinen kuvaa toimintoa tai menetelmää, joka laskee toistuvasti pienemmän osan itsestään lopputuloksen saavuttamiseksi. Se on samanlainen kuin iterointi, mutta sen sijaan, että toistettaisiin joukko toimintoja, rekursiivinen funktio suorittaa toiston viittaamalla itseensä omassa määritelmässään. Rekursiivisen ohjelmoinnin käsitettä voi olla vaikea ymmärtää aluksi, mutta sen hallitseminen voi olla erittäin hyödyllistä. Rekursio on yksi tietotekniikan perustyökaluista.

Klassinen esimerkki on rekursiivinen menetelmä luvun faktorin laskemiseksi. Kokonaisluvun kerroin n , joka on kirjoitettu nimellä n! , on tulos kertomalla n kaikilla positiivisilla kokonaisluvuilla, jotka ovat pienempiä kuin n. Esimerkiksi 3! = 3 x 2 x 1, jolloin tuloksena on 6 ja 4! = 4 x 3 x 2 x 1, mikä johtaa 24. Tehokas tapa laskea faktori on rekursiivinen funktio.



Alla on esimerkki JavaScriptin kirjoitetusta rekursiivisesta tekijäfunktiosta.

function  factorial  (n) { return (n === 0) ? 1 : n *  factorial  (n-1); }

Kuten näette, osa funktion määritelmää tekijä on seurausta tekijä suoritetaan pienemmälle kokonaisluvulle. Soittamalla itsensä se voi kertoa luvun jokaisella sitä pienemmällä positiivisella luvulla ja palauttaa sitten lopputuloksen. Rekursiivisista funktioista voi olla hyötyä muissa laskelmissa, kuten Fibonacci-lukujen tai suurimman yhteisen jakajan laskemisessa.

Rekursiivisen logiikan käyttämisellä voi olla joitain pudotuksia, mukaan lukien loputtoman silmukan luominen ohjelmointiin. Tästä syystä pakotilan (kuten tekeminen kunnes) käyttäminen auttaa loputtoman silmukan syntymisen mahdollisuutta vähentämään, ellei jopa eliminoimaan. Jos tapahtuu loputon silmukka, se voi aiheuttaa ohjelman käyttävän paljon muistia. Se voi myös aiheuttaa ohjelman, käyttöjärjestelmän tai tietokoneen toiminnan lopettamisen.