Rekurzív sorozat

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés]

Például az an+1=an+n; a1=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 a7=a6+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ó: an= (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[szerkesztés]

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üggvényt az S feletti végtelen sorozatnak nevezünk; esetén pedig az elemet a sorozat i-edik tagjának nevezzük és -vel jelöljük. Magát a sorozatot -vel vagy -nel vagy hasonló módon jelöljük.

Definíció[szerkesztés]

  • Egy S halmaz feletti végtelen sorozatot m-edrendben rekurzívnak nevezünk, ha létezik olyan m-változós
függvény,

mellyel tetszőleges nemnegatív egész indexre

,

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 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[szerkesztés]

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 -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 nm számra is n-edrendben rekurzív a sorozat.

Példák[szerkesztés]

  1. Legyen S = ℕ a természetes számok halmaza, ekkor az függvényt véve, 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 függvényt véve, a 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 . Ekkor a 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 , … sn, sn+1 , sn+sn+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 s2 = f(1) = 1 és 2 = s3 = f(s2) = 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 rekurziót.
    1. Ha például a 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 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 s4 = a-b+c, az ötödik pedig s5 = b-c+(a-b+c) = a , a hatodik s6 = c-(a-b+c)+(a) = c-a+b-c+a = b , a hetedik s7 = (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 s2 = g(s1) = g(0) = 0 és s3 = g(s2) = 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[szerkesztés]

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

Az elem-m-est a sorozat i-edik állapotának nevezzük, -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 elemek, ezek tehát meghatározottak, továbbá ekkor is egyértelműen kiszámolható a függvény segítségével, ugyanígy az elemekből , … é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: állapotból a következő, k+1-edik elem is kiszámolható: .

Periodikus és rekurzív sorozatok[szerkesztés]

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:

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

Külső hivatkozások[szerkesztés]