rekursiooniga

Rekursiooniga on programmeerimise ja matemaatika lähenemine, mille korral lahendus leitakse soovitud probleemile läbi sama vormi rakendamise väiksemale, sarnasele alamprobleemile. Rekursioonile on iseloomulik kaks osa: alusjuhtum, mis lõpetab korduste voo, ja rekursiivne samm, kus lahendus jaguneb väiksemaks probleemiks ning funktsioon kutsub ennast tagasi.

Näited rekursioonist on faktoriaal ja fibonaci jada. Faktoriaal n! on defineeritud kui n × (n−1)!, alusjuhtum on 0! = 1. Fibonaci jada puhul kehtivad reeglid F(n) = F(n−1) + F(n−2) koos alusjuhtumitega F(0)=0 ja F(1)=1. Rekursiooni kasutatakse ka puude ja graafide läbimisel (näiteks pre- või postorder läbimine), lahenduste jaotusel ning probleemi jagamisel alamprobleemideks, mida lahendatakse ühesuguse meetodiga.

Eelised on koodis ilme ja loogilise struktuuri lihtsus ning probleemi loomuliku kirjelduse peegeldus. Puudused hõlmavad kõrgemat mälu ning virna kasutust ja võimalikku aeglustumist, kui alamprobleeme lahendatakse mitu korda ilma salvestuseta (korduvate tulemuste arv). Mitmes keeltes on lõpprekursiooni optimeerimine (tail recursion) võimalik, mis võimaldab rekursiooni käivitada efektiivsemalt, kuid see ei kehti kõigil keeltes. Tõhusamaks muutmiseks kasutavad paljud programmeerijad memoiseerimist või dünaamilist programmeerimist, mis salvestab varasemad tulemused ning vältib liigset kordamist. Rekursiooni õigel kasutamisel pakub see selget ja loogilist lahendust, eriti probleemi loogilise struktuuri peegeldamisel.