rekursioon

Rekursioon on arvutusmeetod ning matemaatiline kontseptsioon, mille korral probleem lahendatakse kutsudes lahenduse iseenda sarnase probleemi kaudu. Rekursiivne määratlus koosneb baasjuhtumist, mille korral lahendus antakse otse, ja rekursiivsest sammust, kus probleem lahendatakse väiksema või lihtsama versioonina ning kutsutakse sama meetodit uuesti.

Käitumine on järgmine: rekursiivne funktsioon kontrollib esmalt baasjuhtumit; kui see kehtib, tagastatakse väärtus. Vastasel juhul arvutatakse osa lahendusest ja kutsutakse funktsioon end uuesti väiksema sisendiga ning tulemused ühendatakse. Kirjeldus rõhutab, et rekursioon lõpeb baasjuhtumi jõudmisega; vastasel juhul võib toimuda lõpmatu kutsuvärk, mille tõttu tekib mälus virn (stack overflow).

Näited: faktoriaal n! on defineeritud kui n × (n-1)!, kus n ≤ 1 korral tagastatakse 1; muul juhul n × factorial(n-1). Veel üks näide on Fibonacci järjend, kus F(n) = F(n-1) + F(n-2) ning baasjuhtumid on F(0) = 0 ja F(1) = 1.

Eriliigid ja optimeerimised hõlmavad lõpprekursiooni (tail recursion), kus rekursiivne kutse on viimasel real, võimaldades mõnedes keeltes mälu optimeerida, ning vastastikku rekursiooni, kus kaks või enam funktsiooni kutsuvad üksteist. Rekursiooni kasutatakse laialdaselt loogikas, puude ja graafide läbimisel, ja divide-and-conquer algoritmides nagu mergesort ning kiire sort, samuti matemaatiliste definitsioonide formaliseerimisel. Piirangud hõlmavad suurema mälukasutuse ja võimalikku aeglasust võrreldes iteratiivsete lahendustega.