Rekursiivne funktsioon: FUNCTION Fibo(N: Byte): Longint; VAR Jargmine, Eelmine: Longint; BEGIN IF (N = 0) OR (N = 1) THEN BEGIN Fibo := N; Exit; END; Jargmine := Fibo(N - 1); Eelmine := Fibo(N - 2); Fibo := Eelmine + Jargmine; END; { Fibo } Ülesanne: teha ise täitmise analüüs. Probleemide rekursiivne lahendamine Kuidas arendada välja rekursiivset algoritmi? See pole eesmärk omaette, seda enam, et enamik probleeme laheneb teisiti lihtsamalt. Kuid on n.-ö. rekursiivseid probleeme, mille rekursiivne lahendus on loogilisem, elegantsem ja lihtsam. Kuidas ära tunda, et tasub môelda rekursioonile, s.t. millised on rekursiivse ülesande tunnusjooned? Olgu n! jälle baasnäiteks, kuigi sellegi ülesande mitterekursiivne lahendus on parem. (1) palju ühelaadseid operatsioone, mille "mahukus" on erinev: 0!, 1!, 2!, 3!, . . . (2) saame eristada mitterekursiivset triviaalset erijuhtu: 0! = 1 (3) probleem "keerukamal" juhul on taandatav "lihtsama" juhu lahendamisele: n
4. Generatiivne grammatika ja keeleomandamine Generativistid usuvad, et on olemas iseseisev sünnipärane keeleorgan. Kui inimene kõneleb või kuuleb kõnet, siis aktiveerub proka-piirkond. Algsed argumendid, miks seda sünnipäraseks pidama hakati, on formaalsed. Chomsky keele omandamise paradoks ehk Platoni probleem: 1) süntaks on produktiivne, rekursiivne ja lõpmatu süsteem. Kuna ta on rekursiivne, siis ka lõpmatu 2) rekursiivseid probleeme ei saa omandada 3) kuna kõik inimesed omandavad kõik keele ja kõigil on keelepädevus olemas, siis järelikult on see kaasa sündinud, võimaldamaks lõpmatut süsteemi omandada. Miks pole võimalik loogiliselt keelelauseid ära õppida? Ükski inimene ei saa terve oma elu jooksul kuulda kõiki võimalikke keelelauseid, mistõttu pole kindlust, et ta on kuulnud piisavalt infot, et oma grammatikat konstrueerida. Iga uus info võib tema
..,xn) = a) y, mis on vähim selline element, et g(x1,...,xn,y) = 0 ja iga z < y korral g(x ,...,xn,z) on määratud ja pole 0; b) pole määratud, vastasel juhul. Ehk y on esimene element, mille puhul g(x1,...,xn,y) = 0. Funktsiooni f esitatakse sel juhil operaatortermi abil selliselt: f = μy [g]. DEF: Osaliselt rekursiivsed funktsioonid on konstrueeritavad elementaarfunktsioonidest superpositsiooni-, rekursiooni- ja minimeerimisoperaatori abil. DEF: Kõikjal määratud rekursiivseid funktsioone nimetatakse täisrekursiivseteks funktsioonideks. 20 Cantori funktsioonid. Arvutatava funktsiooni ühekohalised esindajad. Cantori funktsioon (kahekohaline) seab igale naturaalarvude paarile vastavusse tema koodi: c(x,y) = 0,5(x +y)(x+y+1)+x. Leiduvad ka pöördfunktsioonid koodile vastava naturaalarvu leidmiseks. l(c(x, y)) = x; r(c(x, y)) = y c3(x,y,z) = c(x,c(y,z)) cm(x1,x2,...,xm) = c(x1,cm−1(x2,...,xm)) Funktsioonid cm,c1m,c2m,...,cmm on lihtrekursiivsed.
minimeerimisoperaatori y abil f = y[g] abil, kui kogu määramispiirkonnas
y, kus y on min element, et g(x1,..xn,y) = 0, kusjuures iga z
annaabi.ee 
