Rikuro

eta|200ra| Triangulo de Sierpinski - Rikuro de trianguloj, kiuj kreas Fraktalon 
eta|Rikuro kreita helpe de ekrankapta softvaro, kiu kaptas sin mem dum funkciado
eta|Desegno de arbo uzanta rikuran funkcion, skribitan en la logoo
Rikuro (el lat. recurrere, kuri returne) en logiko, matematiko kaj programado estas difino de funkcio, kiu inkluzivas la difinatan funkcion. Ĉiu rikura difino bezonas almenaŭ unu kazon nerikuran. Pli ĝenerale, oni uzas la terminon por iu sekvenco de objektoj, ripetiĝantaj je mem-simila maniero. Ekzemple, se oni aranĝas du spegulojn paralele, la aro de reflektoj, reflektoj de reflektoj, reflektoj de reflektoj de reflektoj ktp estus ekzemplo de nefinia rikuro.

 Formalaj difinoj 
Rikuro estas klaso de objektoj aŭ metodoj difinitaj per simpla baza kazo (almenaŭ unu) kaj aro de reguloj, kiuj reduktas ĉiujn sekvajn kazojn ĝis baza(j) kazo(j). La algoritmon de rikuro oni povas esprimi jene:
 Ĉu estas fino? Rikura procedo kutime havas finan kondiĉon, plej ofte kiam la problemo estas reduktita al la baza kazo. Se tiu kondiĉo ne estas difinita, temas pri nefinia rikuro.
 Se la fina kondiĉo ankoraŭ ne okazis, apliku la regulon de simpligo kaj redoni simpligitan problemon.

 Rikuro en matematiko 
En matematiko rikuro estas vaste uzata por difini arojn, funkciojn kaj por pruvi teoremojn.

 Ekzemploj de rikure difinitaj aroj 
 Naturaj nombroj 
La plej klasika rikure difinita aro estas ankaŭ la plej konata - la aro de naturaj nombroj:
Baza kazo:

Regulo:
se , do ankaŭ 

La aro de naturaj nombroj estas la plej malgranda aro, kiu akordas kun tiuj du ecoj.

 Nombroj de Fibonaĉi 
Alia klasika ekzemplo de rikura difino estas la aro de fibonaĉi-nombroj:

En tiu ekzemplo ni havas du bazajn kazojn - 0 kaj 1.

 Ekzemploj de rikure difinitaj funkcioj 
 Faktorialo 
Faktorialo n! de natura nombro n estas la produto de ĉiuj pozitivaj entjeroj malpliaj aŭ egalaj al n. Formala difino estas jena:

Aldone, oni difinas ke

kaj

Uzante la lastan kiel bazan kazon, oni povas difini faktorialon de ĉiu naturalo rikure:

 Funkcio de Ackermann-Péter 
Funkcio de Ackermann-Péter (akermana funkcio) estas klasika plej simpla ekzemplo de funkcio, kiu estas komputebla, sed ne primitive rikura - t.e. oni ne povas difini ĝin sen rikuro (kvankam jam ekzistas pruvitaj manieroj esprimi ĝin per aliaj metodoj). La funkcio, por nenegativaj entjeroj m kaj n, difiniĝas jene:

Evidentas, ke la funkcio kreskas treege rapide kaj produktas enormajn nombrojn eĉ kun sufiĉe malgrandaj valoroj de m kaj n. Ekzemple, A(4,2) estas entjero konsistanta el 19,729 ciferoj en dekuma sistemo. Por pli grandaj valoroj oni uzas specialajn notaciojn kiel hiperoperatoro, notacio de Knuth, notacio de Conway ktp.

 Aliaj ekzemploj 
 Katalunaj nombroj
 Polinomo de Hermite
 Polinomo de Legendre
 Simbolo de Newton
 Triangulo de Sierpinski
 Komputo de ekonomia interezo

 Rikuraj solvoj kaj pruvoj 
 Lingvaj notoj 
En matematiko ekzistas du malsamaj nocioj: rikuro, kiu kutime priskribas simplajn ("rikurajn", iteraciajn) procedurojn en elementa matematiko; kaj rekursio, kiu traktas rekursiajn funkciojn, kiuj povas esti tipe primitive rekursiaj, parte rekursiaj kaj totale rekursiaj. La teorio de rekursiaj funkcioj estas grava parto de teorio de komputado kaj aliaj branĉoj de komputoscienco, ,kaj konstrua matematiko. Aliflanke, "rikura" estas termino neesenca, kiu priskribas unu tipon de iteraciado.

En Esperanto tiujn du konceptojn oni kelkfoje miksas en nefakaj tekstoj kaj vortaroj. Ekzemple:

 PIV de 2002 havas la terminon "rekursio"Rekursio en NPIV , kaj simple aludas al "rekurso"Rekurso en NPIV , kiu havas "rikuro" kiel unu difinon.

 Komputeko donas la terminojn "rikuro" kaj "rekursio".

 Aliflanke, Komputada Leksikono prave kaj trafe priskribas la diferencon inter terminoj "rekursio" kaj "rikuro".

Ambaŭ terminoj "rekursio" kaj "rikuro" ne estas oficialaj, same kiel preskaŭ ĉiuj fakterminoj.

 Referencoj 

 Vidu ankaŭ 
 Rekursio
 Fraktalo
 Matematika indukto
 Peter Naur
 Transfinia rikuro
 mise en abyme

 Notoj kaj referencoj 


Kategorio:Rikuro
Kategorio:Matematiko
Kategorio:Komputiko
Kategorio:Programado