Primitīvi rekursīvās funkcijas

Rekursīvās funkcijas (no vēlās lat.val. recursio – atgriešanās), nosaukums, kas iestiprinājies zem viena no visvairāk izplatītākajiem variantiem, vispārēju saprotot ar to aritmētisku algoritmu, t.i., tādu algoritmu, kura gala dotie ir naturālo skaitļu sistēmas, bet iespējamie izmantošanas rezultāti ir naturālie skaitļi. Rekursīvās funkcijas ievadīja S.K. Klinī 20.gs. 30. tajos gados, kas, savukārt, balstījās uz Ž.Erbrana, K. Gedeļa u.c. matemātiķu pētījumiem.

Katra rekursīvā funkcija tiek noteikta pēc gala sistēmas vienādojumiem, tās nozīme tiek noteikta ar šo vienādojumu sistēmu palīdzību pēc noteikti formulētiem likumiem, turklāt tādā veidā, ka gala rezultātā dotās rekursīvās funkcijas noteikšanai rodas noteikta tipa algoritms.

Aritmētiskās funkcijas, kuru nozīmes noteikšanai ir kaut kādi algoritmi, ir pieņemts saukt par izskaitļojamām. Izskaitļojamām funkcijām matemātikā ir ļoti liela nozīme. Līdz ar to, ja algoritma izpratnei netiks dota noteikta jēga, izskaitļojamās funkcijas izpratne kļūs neskaidra. Rekursīvās funkcijas jau pēc sava rakstura ir izskaitļojamās funkcijas. Zināmā mērā patiess ir arī pretējs: ir nopietni iemesli, lai domātu, ka matemātiskā rekursivitātes izpratne pēc sava rakstura ir tiešs ekvivalents uz nedaudz neskaidras izskaitļojamības izpratnes fona. Piedāvājums uzskatīt izskaitļojamības izpratni, pēc apjoma sakrītošu ar rekursivitātes izpratni, rekursīvās funkcijas teorijā ir Čērča tēze, kura tiek piedēvēta amerikāņu matemātiķim A.Čērčam, pirmoreiz (20.gs. 30.tajos gados), kas it kā noformulēja un izvirzīja šo priekšlikumu. Čērča tēzes pieņemšana ļauj piedēvēt izskaitļojamās aritmētiskās funkcijas izpratnei tiešu matemātisku jēgu un nodot so izpratni izpētei ar tiešo metožu palīdzību.

Rekursīvās funkcijas ir daļējas funkcijas, t.i., funkcijas, kuras ne vienmēr ir noteiktas. Lai pasvītrotu šo apstākli, bieži vien kā sinonīmu lieto terminu „daļēji rekursīvās funkcijas”. Rekursīvās funkcijas, kas ir nosakāmas, pateicoties jebkuriem argumentiem, sauc par vispārīgi rekursīvām funkcijām.