Rekurzija

Rekúrzija v matematiki in računalništvu pomeni podajanje funkcije na tak način, da se v definiciji sklicujemo na to isto funkcijo (vendar pri drugačnem argumentu). Tak način podajanja imenujemo rekurzivno podajanje ali rekurzivna formula (tudi rekurzivna definicija). Beseda rekurzívno (latinsko recurrere, kar pomeni teči nazaj) pomeni nanašajoče na samega sebe.

Najpogosteje srečamo rekurzijo pri zaporedjih, kjer je n-ti člen določen z enim ali več predhodnimi členi. Rekurzija se uporablja tudi v programiranju.

Če želimo, da je rekurzivna definicija zaporedja (funkcije) sploh smiselna, moramo poleg rekurzivne formule podati tudi vrednost vsaj enega začetnega člena.

Tudi v vsakdanjem življenju srečamo rekurzijo.

• Definicija prednika neke osebe je lahko:
  • prednik osebe je eden od roditeljev osebe (osnovni primer)
  • prednik pa je tudi roditelj kateregakoli prednika (rekurzivni primer)

• Ena od opredelitev športa pravi:

  Praktično gledano lahko šport definiramo skozi vsakodnevno uporabo izraza šport.

Rekurzijo si lahko predstavimo tudi z geometrijskimi figurami, ki so določene rekurzivno: Kochova snežinka, trikotnik Sierpinskega, Cantorjeva množica, fraktali ...

Razširjena šala na temo rekurzije je definicija:
rekurzija, glej rekurzija.

Nekaj najbolj znanih rekurzivnih formul pri matematičnih zaporedjih:

• aritmetično zaporedje (za poljuben a₁ in d)

${\displaystyle a_{n}=a_{n-1}+d\,\!}$

• geometrijsko zaporedje (za poljuben a₁ in k)

${\displaystyle a_{n}=a_{n-1}\cdot k\,\!}$

• fakulteta

${\displaystyle F_{0}=1\,}$

${\displaystyle F_{n}=nF_{n-1}\,}$

• Fibonaccijevo zaporedje

${\displaystyle F_{0}=0\,}$

${\displaystyle F_{1}=1\,}$

${\displaystyle F_{n}=F_{n-1}+F_{n-2}\,}$

• Fermatova števila

${\displaystyle F_{n}=(F_{n-1}-1)^{2}+1\,}$

${\displaystyle F_{n}=F_{n-1}+2^{2^{n-1}}F_{0}\cdots F_{n-2}\,}$

${\displaystyle F_{n}=F_{n-1}^{2}-2(F_{n-2}-1)^{2}\,}$

${\displaystyle F_{n}=F_{0}\cdots F_{n-1}+2\,}$

za n ≥ 2.

• Catalanova števila

${\displaystyle C_{0}=1\qquad {\mbox{in}}\qquad C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}\quad {\mbox{za }}n\geq 1.}$

• Schröderjeva števila

${\displaystyle S_{0}=1\qquad {\mbox{ in }}\qquad S_{n}=S_{n-1}+\sum _{i=0}^{n-1}S_{i}S_{n-1-i}\quad {\mbox{ za }}n\geq 1\;.}$

• največji skupni delitelj (D) dveh pozitivnih števil:

D(n, n) = n

D(n, k) = D(n - k, k) za n > k

D(n, k) = D(k, n) za n < k

• trikotniška števila

${\displaystyle T_{1}=1\,}$

${\displaystyle T_{n}=T_{n-1}+n\,}$

• trikotniška kvadratna števila

${\displaystyle N_{0}=0\,}$

${\displaystyle N_{1}=1\,}$

${\displaystyle N_{n}=34\,N_{n-1}-N_{n-2}+2\,}$

• Ackermannova funkcija
• hanojski stolpi
• rekurzivne podatkovne strukture

• rekurzija
• samopodobnost
• samosklic
• iteracija
• Fibonaccijevo število
• fraktal
• Thue-Morsejevo zaporedje
• rekurzivni akronim

Ta matematični članek je škrbina. Pomagajte Wikipediji in ga razširite.

• p
• p
• u