rekursi/o ^KompLeks

rekursio

: Tia maniero difini funkcion aŭ komputan proceduron, ke la difinato eventuale povas referenci sin mem: senfina rekursio (ekz-e kaŭzita de cirkla difino).

Rim.: Kaj „rekursio“, kaj „rikuro“ etimologie signifas „retroiro“, t.e. reveno al la antaŭe komputitaj valoroj de iu vico por komputi la sekvan. Pri la termino „rekursio“ tiu koncepto ne plu validas: rekursia komputo povas anticipe ekzameni ankaŭ siajn „postajn“ valorojn, eĉ plenumi elĉerpan serĉon tra ili. Tion oni neniam faras en la klasika matematiko, por kies bezonoj plene sufiĉas rikuro, koncepto logike pli sekura. [Sergio Pokrovskij]

angle:: recursion senfina ~o: infinite recursion.
beloruse:: рэкурсія senfina ~o: бясконцая рэкурсія.
ĉine:: 递推 [dìtuī], 遞推 [dìtuī], 递归 [dìguī], 遞歸 [dìguī]
pole:: rekurencja
ruse:: рекурсия senfina ~o: бесконечная рекурсия.
ukraine:: рекурсія

rekursia

: Uzanta rekursion, karakterizata de rekursio: rekursia proceduro (programlingva proceduro² kiu eventuale vokas sin mem dum la rultempo); rikura¹

angle:: recursive ~a proceduro: recursive procedure.
beloruse:: рэкурсіўны ~a proceduro: рэкурсіўная працэдура.
ĉine:: 递推 [dìtuī], 遞推 [dìtuī], 递归 [dìguī], 遞歸 [dìguī]
pole:: rekurencyjny, zagnieżdżony
ruse:: рекурсивный ~a proceduro: рекурсивная процедура.
ukraine:: рекурсивний

rekursia funkcio

: Unu el la matematikaj precizigoj de la intuicia koncepto pri komputeblo. Oni reduktas ĉiujn komputajn problemojn al naturnombraj funkcioj³ `N^n ->N`, kaj konstruas hierarkion el 3 subklasoj: primitive rekursiaj funkcioj, ĉieaj rekursiaj funkcioj, μ-rekursiaj funkcioj. La lasta klaso estas la plej ĝenerala, ĝi entenas la du aliajn kaj reprezentas ĉiujn komputeblajn funkciojn. Se oni diras simple „rekursia funkcio“, tiam oni celas ĝuste tiun ĉi klason: simbole la hierarkion de la rekursiaj funkcioj eblas prezenti per la formulo `"PRF" sub "ĈRF" sub "MRF"`; estas pruvite, ke la klaso da rekursiaj funkcioj, la klaso da funkcioj difineblaj per Turinga aŭtomato, per λ-kalkulo, per la Markovaj ĉenoj estas ĉiuj egalaj.

angle:: recursive function
beloruse:: рэкурсіўная функцыя
pole:: funkcja rekurencyjna (mat.)
ruse:: рекурсивная функция

primitive rekursia funkcio, PRF

: La difino estas rikura^1.b: oni difinas la bazan klason kaj du operatorojn. La bazaj funkcioj estas: la konstanta funkcio `O(x)=0`; la alkremento `S(x)=x+1`; la projekcioj `"Pr"[m,n](x_1,...x_n)=x_m,1 le m le n`. La operatoroj estas la kunligo² kaj la primitiva rekursiilo. Primitive rekursia funkcio estas baza primitive rekursia funkcio aŭ rezulto de finifoja apliko de la operatoro(j): `S(S(x))` estas primitive rekursia funkcio ĉar ĝi estas kunligo de du alkrenentoj (ĝi ĵetas `x to x+2`); ĉiuj primitive rekursiaj funkcioj estas ĉieaj funkcioj; pliopo da nombroteoriaj funkcioj estas primitive rekursiaj funkcioj.

angle:: primitive recursive function
beloruse:: прымітыўна-рэкурсіўная функцыя
pole:: funkcja pierwotnie rekurencyjna
ruse:: примитивно-рекурсивная функция

primitiva rekursiilo

: Operatoro uzata en la difino de primitive rekursia funkcio, simila al nombrila iteracio; la formala difino estas rikura^1.b. Estu `f` funkcio `n`-loka, kaj `g` funkcio `n+2`-loka; tiam apliko de primitiva rekursiilo al la paro da funkcioj `(f,g)` estas tia `n+2`-loka funkcio `h`, ke baze: `h(x_1,...,x_n,0)=f(x_1,...,x_n)`; kaj rikure: `h(x_1,...x_n,y+1)=g(x_1,...x_n,y,h(x_1,...,x_n,y))`. Estu `f(x)="Pr"[1,1](x)=x` kaj `g(x,y,z)=S("Pr"[2,3](x,y,z))=S(y)`. Tiam `h(0,x)=x` kaj `h(S(y),x)=g(y,h(y,x),x)=S(h(y,x))`. Sekve `h(0,1)=1, h(1,1)=S(h(0,1))=2, h(2,1)=S(h(1,1))=3`. Do, `h` estas 2-loka primitive rekursia funkcio, nome „adicio“.

angle:: primitive recursion
beloruse:: апэратар прымітыўнай рэкурсіі
pole:: operator minimalizacji ograniczonej
ruse:: оператор примитивной рекурсии

μ-rekursia funkcio, MRF, parta rekursia funkcio

: Funkcio difinta per la samaj rimedoj, kiel la primitive rekursiaj funkcioj, plus la μ-operatoro de senbara serĉo: ĉar la minimumigo povas diverĝi, tial ne ĉiuj μ-rekursiaj funkcioj estas ĉieaj; ankaŭ nenie difinitaj (ĉie diverĝaj) funkcioj estas partaj rekursiaj funkcioj.

angle:: partial recursive function, >(μ-)recursive function
beloruse:: часткова рэкурсіўная функцыя
pole:: funkcja częściowo rekurencyjna
ruse:: частично рекурсивная функция

ĉiea rekursia funkcio, ĈRF

: μ-rekursia funkcio kiu estas ĉiea funkcio: ĉiu PRF estas ĉiea rekursia funkcio; ekzistas ĉieaj rekursiaj funkcioj kiuj ne estas primitive rekursiaj.

angle:: total recursive function
beloruse:: агульнарэкурсіўная функцыя
pole:: całkowita funkcja rekurencyjna
ruse:: общерекурсивная функция

administraj notoj

~o: Mankas dua fontindiko.
~o: Mankas fonto, kiu estas nek vortaro nek terminaro.
~a: Mankas dua fontindiko.
~a: Mankas fonto, kiu estas nek vortaro nek terminaro.
~a funkcio: Mankas dua fontindiko.
~a funkcio: Mankas fonto, kiu estas nek vortaro nek terminaro.
primitive ~a funkcio, PRF: Mankas dua fontindiko.
primitive ~a funkcio, PRF: Mankas fonto, kiu estas nek vortaro nek terminaro.
primitiva ~ilo: Mankas dua fontindiko.
primitiva ~ilo: Mankas fonto, kiu estas nek vortaro nek terminaro.
μ-~a funkcio, MRF, parta ~a funkcio: Mankas dua fontindiko.
μ-~a funkcio, MRF, parta ~a funkcio: Mankas fonto, kiu estas nek vortaro nek terminaro.
ĉiea ~a funkcio, ĈRF: Mankas dua fontindiko.
ĉiea ~a funkcio, ĈRF: Mankas fonto, kiu estas nek vortaro nek terminaro.

rekursi/o KompLeks