Rekurzív sorozat

A matematikában a rekurzív sorozat egy olyan sorozat, ami definiálható egy rekurziós összefüggés segítségével. Utóbbi olyan képlet, összefüggés, ami a sorozat bármely elemét a megelőző néhány tag ismeretében adja meg (a pontos definíciót lásd lentebb).

Rekurzív vs. explicit képlet

Például az $a_{n+1}=a_{n}+n;a_{1}=0$ rekurzív képlettel definiált sorozat tagjai rendre: $0,1,3,6,10,15,...$ (magyarul: bármely tagot úgy számolj ki, hogy az előző taghoz hozzáadod a sorszámát). Az $a_{7}=a_{6}+6=21$ tagot csak akkor tudjuk kiszámolni, ha előbb a hatodik tagot már kiszámoltuk. E sorozatra azonban explicit (a megelőző tagok ismeretét nem kívánó) képlet is adható: $a_{n}=(n-1)*n/2$. Sokszor épp az okoz gondot, hogy csak a megelőző tagok ismeretében tudunk számolni (ha az explicit képletet nehezebb megtalálni); ezért ha például egy számszerűen ismeretlen rekurzív sorozat $10000$. tagját kívánjuk ismerni, akkor előtte mind a $9999$ megelőző tagot végig kell számolni.

Tehát a fogalomnak bizonyos értelemben ellenpárja az általánosan, képlettel megadott sorozat fogalma, mely utóbbi azt jelenti, hogy ha kíváncsiak vagyunk a sorozat valamely tagjára/elemére, azt az előző tagok ismerete nélkül is, explicite ki tudjuk számolni. Azonban, mint a fenti példából látható, a félrevezető név ellenére egy sorozat rekurzivitása nem az egyes sorozatok egy immanens tulajdonsága, hanem pusztán egy megadási mód (egy lehetséges a sok közül).

A két fogalom (rekurzív-explicit) szembeállítása elmosódott és pragmatikus (azaz matematikailag nehezen lenne precízen értelmezhető, mivel gyakorlatilag minden függvény és sorozat, már a természetes számok $1,2,3,...$ sorozata is tkp. rekurzív); de a gyakorlatban fontos ez a megkülönböztetés. Bizonyos esetekben a rekurzív sorozat elemei kiszámíthatók zárt alakos kifejezéssel is (az előző tagok ismerete nélkül), ilyenek például a lineáris rekurzióval definiált sorozatok, mint amilyen a Fibonacci-számok sorozata is.

Alkalmazások

Mind a rekurzív sorozat fogalma, mind a fenti probléma a matematika szinte minden ágában előfordul (de különösen a számítógéptudományban, a kombinatorikában, a numerikus analízisben és az elemi matematikában), de az informatika számára is nagyon fontos, mivel az általános tagot számítgató emberrel ellentétben a gépek viszont a rekurzív sorozatokkal boldogulnak jobban.

Jelölések és előzetes megállapodások: Adott $S$ halmazba képező, a természetes számok (esetleg a pozitív egész számok) halmazán értelmezett $f:\mathbb {N} \to S$ függvényt az $S$ feletti végtelen sorozatnak nevezünk; $i\in \mathbb {N}$ esetén pedig az $f(i)\in S$ elemet a sorozat $i$-edik tagjának nevezzük és $s_{i}$-vel jelöljük. Magát a sorozatot $\left\{s_{i}\right\}$-vel vagy $\left(s_{i}\right)_{i\in \mathbb {N} }$-nel vagy hasonló módon jelöljük.

Definíció

• Egy $S$ halmaz feletti $(s_{i})_{i\in \mathbb {N} }=(s_{0},s_{1},s_{2},\ldots ,s_{i},\ldots )$ végtelen sorozatot m-edrendben rekurzívnak nevezünk, ha létezik olyan m-változós

$\varphi \!:S^{m}\to S$ függvény,

mellyel tetszőleges nemnegatív egész $i$ indexre

$s_{i+m}=\varphi \left(s_{i},s_{i+1},\ldots ,s_{i+m-1}\right)$,

tehát ha a sorozat bármely tagja a megelőző m darab tagból a fenti m-változós függvény segítségével számolható ki. A $\varphi$ függvény a rekurziós szabály (-előírás, -összefüggés, -kapcsolat, egyenlet stb.). Arról van szó tehát, hogy a sorozat bármely tagja az őt megelőző m darab tagból számítható ki valamilyen módon.

Rend

Egy sorozatot akkor nevezünk (minden további jelző nélkül) rekurzívnak, ha van olyan m pozitív természetes szám, amelyre nézve m-edrendben rekurzív. Ha van ilyen pozitív szám, akkor a (pozitív) természetes számok halmazának jólrendezettsége miatt – azaz amiatt, hogy a pozitív természetes számok nem üres halmazában van egy legkisebb elem – van legkisebb ilyen pozitív szám is, melyet a sorozat minimális rekurziós rendjének nevezünk, és $o\left(f\right)$-fel jelölünk (az o betű utalás a latin ordo = rend szóra). A minimális rekurziós rend egyértelmű, de ettől eltekintve egy sorozat ha m-rendben rekurzív, attól lehet más rendben is rekurzív: belátható, hogy ha a minimális rekurziós rend m, akkor minden ennél nagyobb n≥m számra is n-edrendben rekurzív a sorozat.

Példák

1. Legyen S = ℕ a természetes számok halmaza, ekkor az $\phi _{1}:\mathbb {N} \to \mathbb {N} ;\phi _{1}(n):=n+1$ függvényt véve, $s_{1}:=0$ esetén a következő elsőrendben rekurzív sorozatot kapjuk: 0, 1, 2, 3, 4, … ; ennek értékkészlete a természetes számok halmaza.
2. Legyen S = ℕ, és j∈ℕ rögzített természetes szám; a $\phi _{j}(n):\mathbb {N} \to \mathbb {N} ;\phi _{j}(n):=n+j$ függvényt véve, a $s_{1}:=0$ megállapodással a 0, 0+j = j, j+j = 2j, 2j+j = 3j , … egyszóval a 0, j, 2j, 3j , … sorozatot kapjuk, vagyis a j-vel osztható számok sorozatát.
3. Legyen S = ℕ, és $\Phi (n,m):\mathbb {N} ^{2}\to \mathbb {N} ;\Phi (n,m):=n+m$ . Ekkor a $s_{1}:=1,s_{2}:=1$ megállapodással a következő másodrendben rekurzív sorozatot kapjuk: 1, 1, 1+1 = 2 , 1+2 = 3 , 2+3 = 5, 3+5 = 8 , … s_n, s_n+1 , s_n+s_n+1 , … sorozatot kapjuk; minden elem a két megelőző elem összege. ez a híres Fibonacci-sorozat (1, 1, 2, 3, 5, 8, 13, 21, 34 , …), amely másodrendben rekurzív. Minimális rekurziós rendje is 2, ugyanis nem állítható elő egyváltozós f(n) függvény segítségével rekurzív módon; mivel s₂ = f(1) = 1 és 2 = s₃ = f(s₂) = f(1) miatt f(n) az n = 1 helyen az 1 és 2 értéket is fel kellene hogy vegye, így nem (lenne) függvény.
4. Adott rekurzióval számított sorozatok esetén a kezdőelemek (a kezdőállapot) megválasztása hatással lehet a minimális rekurziós rendre. Legyen most S = ℤ, és tekintsük a $\psi (a,b,c):\mathbb {N} ^{3}\to \mathbb {N} ;\psi (a,b,c):=a-b+c$ rekurziót.
   1. Ha például a $s_{1}:=0,s_{2}:=0,s_{3}:=0$ megállapodással indítunk, akkor a sorozat összes értéke 0 lesz: 0,0,0, 0-0+0 = 0, 0-0+0 = 0, … , tehát a csupa 0-ból álló sorozatot kapjuk. Ez viszont már elsőrendben is rekurzív.
   2. Ha meg például az $s_{1}:=0,s_{2}:=0,s_{3}:=1$ megállapodással indítunk, akkor a sorozat periodikus lesz : 0,0,1, 0-0+1 = 1, 0-1+1 = 0, 1-1+0 = 0, 1-0+0 = 1, 0-0+1 = 1 , …; tehát a 0,0,1,1,0,0,1,1, … sorozatot kapjuk. Ez nem meglepő, hisz a sorozat első három a,b,c tagját bárhogy is megválasztva a negyedik tag s₄ = a-b+c, az ötödik pedig s₅ = b-c+(a-b+c) = a , a hatodik s₆ = c-(a-b+c)+(a) = c-a+b-c+a = b , a hetedik s₇ = (a-b+c)-(a)+b = c, tehát a sorozat így néz ki: a,b,c,a-b+c, a,b,c,a-b+c … Másrészt ez a sorozat már 2-rendben is rekurzív, ugyanis a kétváltozós f(x,y)=1-x függvény is generálja (ez csak egy változótól függ igazán, de két változós). A sorozat minimális rekurziós rendje pedig 2, mert egyváltozós g(x) függvény nem generálja: ugyanis s₂ = g(s₁) = g(0) = 0 és s₃ = g(s₂) = g(0) = 1 is teljesülne, azaz g(0) = 0 = 1, márpedig nem igaz, hogy 0 = 1.
   3. Belátható azonban, hogy bármilyen kezdőelemekből is induljunk ki, a fenti rekurzióval adott sorozatok mindig már másodrendben is rekurzívak lesznek, bármilyen, az f(a,b) = c; f(b,c) = a-b+c; f(c, a-b+c) = a , f(a-b+c,a) = b előírással értelmezett függvénnyel. Némi számolással ellenőrizhető, hogy ilyen függvény létezik (ha (x,y)=(x',y'), akkor f(x,y)=f(x',y') teljesül, amennyiben (x,y) a fent megnevezett rendezett párok közül kerülnek ki), egy konkrét példánya pedig valamilyen interpolációs eljárással kereshető (utóbbi esetben a függvény egy polinom lesz); vagy akár a megnevezett rendezett párok kivételével akár mindenütt máshol 1-nek is definiálható.

A rekurzív sorozat állapotai

E szakasz szerint egy m-edrendű rekurzív sorozatot (ahogy az sejthető) az első m eleme tökéletesen meghatározza.

Az $s^{i}:=\left(s_{i},s_{i+1},...,s_{i+m-1}\right)$ elem-m-est a sorozat i-edik állapotának nevezzük, $s^{0}:=\left(s_{0},s_{1},...,s_{m-1}\right)$ -et, tehát az első m db. elemét (az első állapotot) kezdőállapotnak. Belátható, hogy a kezdőállapot egyértelműen meghatározza a rekurzív sorozat bármelyik elemét, tehát az egész sorozatot; a k-adik állapot pedig a sorozat bármely, k-nál nagyobb (ti. nem kisebb) indexű elemét.

Előbbi, kezdőállapotra vonatkozó tétel teljes indukcióval látható be (az azt követő állítás is, hasonlóan): adottak az $s^{1}:=\left(s_{1},s_{2}...,s_{m-1},s_{m}\right)$ elemek, ezek tehát meghatározottak, továbbá ekkor $s_{m+1}=\varphi \left(s_{1},s_{2},...,s_{m}\right)$ is egyértelműen kiszámolható a $\varphi$ függvény segítségével, ugyanígy az $s^{2}:=\left(s_{2},s_{3},...,s_{m+1}\right)$ elemekből $s_{m+2}=\varphi \left(s_{2},s_{3},...,s_{m+1}\right)$, … és ha már valamilyen k-ra (k ≥ m) ismerjük a sorozat összes elemét, akkor az utolsó, k-adik elemtől visszafelé számolva, az utolsó m db. elemből: $s^{k-m+1}:=\left(s_{k-(m-1)},...,s_{k-1},s_{k}\right)=\left(s_{k-m+1},s_{k-m+2},...,s_{k-m+m}\right)$ állapotból a következő, k+1-edik elem is kiszámolható: $s_{k+1}:=\varphi \left(s_{k-m+1},s_{k-m+2},...,s_{k}\right)$.

Periodikus és rekurzív sorozatok

Belátható, hogy ha egy S-sorozat a k küszöbindextől kezdve periodikus a p (minimális) periódussal, akkor rekurzív, és rendje legfeljebb a küszöbindex és a periódus összege:

$o(f)\leq p+k$

Érdekes, hogy ha S véges halmaz (elemeinek száma N), akkor tkp. fordítva is igaz: ha $f$ rekurzív, akkor periodikus is, és minimális p periódusára érvényes

$p\leq p+k\leq \left|S\right|^{o(f)}=N^{o(f)}$

Külső hivatkozások

• Sulinet-oldal a rekurzív sorozatokról
• PDF jegyzet (Gonda János)