Rekursiivsed

Rekursiivsus on kontseptsioon, kus lahendus viitab iseendale. Programmide kontekstis tähendab rekursiivne meetod või funktsioon probleemi lahendamist, jagades selle alamprobleemideks, mis on samas vormis kui algne probleem.

Baasjuhtum on rekursiooni lõpetav juhtum, mis ei vaja enam rekursiivset kutset. Rekursiivne samm kutsub funktsiooni uuesti väiksema või lihtsama alamprobleemi lahendamiseks.

Näide: faktoriaal n! definitsiooniga: n! = n × (n-1)!, kus 0! = 1. Teine klassikaline näide on fibonaci jada, kus F(n) = F(n-1) + F(n-2) koos alustähtedega F(0)=0, F(1)=1.

Rekursiivsed meetodid on laialdaselt kasutusel: puude ja graafide läbikäimisel (preorder, inorder, postorder), jagatud ja vallutavate algoritmide (divide and conquer), rekursiivsel otsimisel ja parsimisel ning erinevate andmestruktuuride, nagu puud, töötlusel.

Rekursioon võib suurete sisendite puhul põhjustada suurenenud staki kasutamist, mis võib viia virnastiku ületamiseni. Paljudes keeltes on lõpprekursiooni optimeerimine (tail-call optimization, TCO), mis võimaldab stakki kasvu piirata või vältida. Kui optimeerimist ei rakendata, võivad suurte sisendite korral jõudlus ja mälu tarvitamine olla piiratud.