Rikuro

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
Rikuro en arto.

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 ne rikuran. 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[redakti | redakti fonton]

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:

  1. Ĉ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.
  2. Se la fina kondiĉo ankoraŭ ne okazis, apliku la regulon de simpligo kaj redoni simpligitan problemon.

Rikuro en matematiko[redakti | redakti fonton]

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

Ekzemploj de rikure difinitaj aroj[redakti | redakti fonton]

Naturaloj[redakti | redakti fonton]

La plej klasika rikure difinita aro estas la plej konata - la aro de naturaloj: Baza kazo:

0 \in \mathbb{N}

Regulo:

se n\in \mathbb{N}, do ankaŭ  n + 1 \in \mathbb{N}

La aro de naturaloj estas la plej malgranda aro, kiu akordas al tiuj du ecoj.

Nombroj de Fibonaĉi[redakti | redakti fonton]

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

 
  F_n := F(n):=
  \begin{cases}
    0             & \mbox{ se } n = 0; \\
    1             & \mbox{ se } n = 1; \\
    F(n-1)+F(n-2) & \mbox{ se } n > 1. \\
   \end{cases}

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

Ekzemploj de rikure difinitaj funkcioj[redakti | redakti fonton]

Faktorialo[redakti | redakti fonton]

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

n! = 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n = \prod_{k=1}^n k

Aldone, oni difinas ke

0! = 1

kaj

1! = 1

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

\begin{cases}
1! = 1 \\
n! = n\cdot(n-1)!
\end{cases}

Funkcio de Ackermann-Péter[redakti | redakti fonton]

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:

 A(m, n) =
 \begin{cases}
 n+1 & \mbox{ se } m = 0 \\
 A(m-1, 1) & \mbox{ se } m > 0 \mbox{ kaj } n = 0 \\
 A(m-1, A(m, n-1)) & \mbox{ se } m > 0 \mbox{ kaj } n > 0
 \end{cases}

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 je 19,729 numeroj en dekuma sistemo[1]. Por pli grandaj valoroj oni uzas specialajn notaciojn kiel hiperoperatoro, notacio de Knuth, notacio de Conway ktp.

Aliaj ekzemploj[redakti | redakti fonton]

Rikuraj solvoj kaj pruvoj[redakti | redakti fonton]

Lingvaj notoj[redakti | redakti fonton]

Estas diversaj terminoj por la koncepto en Esperanto. Ekzemple: PIV de 2002 havas "rekursio", kiu simple aludas "rekurso", kiu havas "rikuro" kiel unu difinon. Komputeko donas "rikuro" kaj "rekursio". Komputada Leksikono donas "rikuro"

"Kurso" estas oficiala radiko; "rekursio", "rikuro" ne estas.

Vidu ankaŭ[redakti | redakti fonton]

Notoj kaj referencoj[redakti | redakti fonton]

  1. Decimal expansion of A(4,2)