Täisrekursiivne funktsioon

Rekursiivsed funktsioonid – ehk funktsioon, mis iseennast välja kutsub. Tihti on selliselt kirjutatud lahendused selgemad ja lühemad kui tsüklitega kirjutatud lahendused. Kõige kasulikumad on rekursiivsed lahendused ülesannetes, mis tegelevad puukujuliste (st. hargnevate) andmestruktuuridega.

Programmeerimises nimetatakse rekursiooniks tavaliselt situatsiooni, kus funktsiooni definitsioonis on kasutatud parasjagu defineeritavat funktsiooni. Kõige lihtsam rekursiivne funktsioon Pythoni keeles oleks järgnev:
 def f():
     f()
Kui sellist funktsiooni Pythonis välja kutsuda, siis vastavalt definitsioonile tuleb kutsuda seesama funktsioon uuesti välja, see omakorda põhjustab jälle selle funktsiooni väljakutsumise. Pythoni puhul lõpeb taoline ahel veateatega, mis ütleb, et alustatud, aga mitte lõpule jõudnud väljakutsete limiit sai täis. (Mõne teise keele puhul võib see protsess lõputult käima jääda.

Baas ja samm

Selleks, et rekursioon mingil hetkel lõppeks, peab rekursiivses funktsioonis toimuma hargnemine sõltuvalt funktsiooni argumentidest. Vähemalt üks haru peab olema ilma rekursiivse väljakutseta – seda nimetatakse rekursiooni baasiks. Seda haru, mis kutsub funktsiooni rekursiivselt välja, nimetatakse rekursiooni sammuks.

Rekursiooni samm lahendab tavaliselt ülesande vähendatud koopia e mingi alamülesande (kasutades selleks sedasama funktsiooni) ning koostab saadud tulemuse põhjal terve ülesande lahenduse. Aga kui alamülesanne on piisavalt väike, siis käsitletakse seda baasjuhuna ja vastus antakse ilma rekursiivse väljakutseta.

Näide: Faktoriaal

Faktoriaali definitsiooni järgi on 0!=1. Iga teise naturaalarvu puhul on n! võrdne arvude 1 kuni n korrutisega. Nt

 4! = 1 × 2 × 3 × 4
 5! = 1 × 2 × 3 × 4 × 5

Nagu näha, on 5! arvutus väga sarnane 4! arvutusele – selleks, et arvutada 5! võiksime me arvutada 4! ja korrutada saadud tulemuse 5-ga. Seda asjaolu arvestades on kirjutatud järgnev rekursiivne faktoriaali funktsioon:
 def fact(n):
     if n == 0:
         return 1
     else: 

 return fact(n-1) * n 

Ajalugu

Täieõiguslik rekursioon sai kujundusvõimaluseks, mida esmalt toetasid trükis Dijkstra (1960) ja McCarthy (1960) ning mida rakendati programmides LISP, ALGOL, PL/I ja Logo (Martin, 1985, Lavallade, 1985), koos märkimisväärsete eranditena Fortran ja COBOL. Seejärel kasutati programmidele tähenduse omistamiseks formaalset loogikat, osa semantikat tugines rekursioonile, nagu süsteemide ümberkirjutamine, kuid teised mitte, nagu hulgateooria või λ-arvutus (kus rekursiooni simuleeritakse fikseeritud punkti kombinaatoritega).

Kuigi Dijkstra (1974) (1975) arvamus varieerus, osutus rekursioon võimsaks vahendiks algoritmide väljendamiseks (Dijkstra, 1999) (Reingold, 2012), eriti rekursiivsetes andmestruktuurides, nagu loendid, pinud ja puud.