Naturaj nombroj

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

${\displaystyle 0\in \mathbb {N} }$

Regulo:

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

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:

${\displaystyle 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.

Faktorialo

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

${\displaystyle n!=1\cdot 2\cdot 3\cdots (n-1)\cdot n=\prod _{k=1}^{n}k}$

Aldone, oni difinas ke

${\displaystyle 0!=1}$

kaj

${\displaystyle 1!=1}$

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

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

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:

${\displaystyle 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

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