Rekurencat

Relacionet rekurente 
Në matematikë, një relacion rekurent është një ekuacion që shpreh termin e n-të të një sekuence në funksion të k termave paraardhës, për një k të fiksuar (të pavarura nga n), që quhet rendi i relacionit. Pasi jepen k termat fillestarë të një sekuence, relacioni i rekurencës lejon llogaritjen e të gjithë termave të atij vargu.
Shpesh termi rekursiv përdoret si sinonim i fjalës “i llogaritshëm” sepse thuhet se një funksion mund të përcaktohet në mënyrë rekursive vetëm nëse ai mund të llogaritet nga ndonjë progam. Në rastin e përgjithshëm, një relacion rekurrent definohet me:


Ku f është një funksion i dhënë.

Relacioni rekurent quhet linear nëse termi i n-të mund të shprehet si funksion linear i termave paraardhës. Rekurenca lineare është homogjene nëse nuk përmban terma që nuk janë shumëfisha të kufizave paraardhëse . 

Kështu, rekurenca lineare homogjene e shkallës k ka formën:

ku  janë numra realë, dhe  është i ndryshëm nga zero.
Ndërsa relacioni rekurent quhet johomogjen nëse ka formën:



ku  janë numra realë dhe  është funksion jo-zero i cili varet vetëm nga n.

 Shembuj 

 Vargu i Fibonaçit 
Rekurenca e rendit të dytë e fituar nga numrat e Fibonaçit është shembull i një relacioni rekurent homogjen. Vargu i Fibonaçit është i definuar me ekuacionin 

dhe kushtet fillestare

alt=Trekëndëshi i Paskalit|parapamje|Trekëndëshi i Paskalit

Në mënyrë të qartë, sekuenca jep ekuacionet
alt=Golden Ration- Vargu i Fibonaçit|parapamje|Golden Ration- Vargu i Fibonaçit

Kështu fitojmë vargun me kufizat fillestare  

Këto kufiza formojnë edhe Relacionin e "Artë" .

Rekurenca mund të zgjidhet me formulën e Binetit, e cila përfshin fuqitë e dy rrënjëve të polinomit karakteristik   dhe fitohet ekuacioni:

 ,

ndërsa funksioni gjenerues i sekuencës është funksioni racional  .

 Kullat e Hanoit 
alt=Kullat e Hanoit 1|parapamje|Kullat e Hanoit 1
Kulla e Hanoit është një enigmë popullore e fundit të shekullit të nëntëmbëdhjetë e shpikur nga matematikani francez Édouard Lucas. Kjo enigmë përbëhet nga tre kunja të montuara në një tabelë së bashku me disqe të madhësive të ndryshme. Fillimisht këto disqe vendosen në kunjin e parë sipas madhësisë, me më të madhin në fund. Rregullat e enigmës lejojnë që disqet të zhvendosen një nga një nga një kunj në tjetrin për sa kohë që një disk nuk është kurrë i vendosur mbi një disk më të vogël. Qëllimi i enigmës është që të gjitha disqet të jenë në kunjin e dytësipas madhësisë, me më të madhin në fund.

Le të jetë  numri i lëvizjeve të nevojshme për të zgjidhur enigmën e Kullës së Hanoit me n disqe. Gjejmë një relacion rekurent për sekuencën .

Fillojmë me  disqe në kunjën e parë. Ne mund t'i transferojmë  disqet e sipërme në kunjën e tretë, duke ndjekur rregullat e enigmës, me  lëvizje. Diskun më të madh e mbajmë të fiksuar gjatë këtyre lëvizjeve. Pastaj, e përdorim një lëvizje për të transferuar diskun më të madh në kunjin e dytë. Së fundmi, i transferojmë  disqet tjera nga kunji 3 në kunjin 2 duke përdorur  lëvizje përsëri. Kjo tregon se enigmën e Kullave të Hanoit me  disqe mund t'a përfundojmë duke përdorur  lëvizje.
alt=Kullat e Hanoit 2|parapamje|Kullat e Hanoit 2
Pra relacioni rekurent i formuar është:



me zgjidhjen e tij fitojmë ekuacionin: 

 Vargu aritmetik dhe vargu gjeometrik 
Vargu aritmetik është vargu i formës  , pra, i cili fillon me një term a dhe secili term i rradhës fitohet duke ia shtuar termit paraardhës numrin d. Kështu vërejmë se vargu aritmetik mund të definohet në mënyre rekurente me

 dhe


Zgjidhja e kësaj rekurence jep ekuacionin:


Ndërsa vargu gjeometrik i cili ka formën  mund të definohet në formë rekursive si:

 dhe


Zgjidhja e të cilit do të ishte: 

 Koeficientët binomialë 
Koeficientët binomialë  , të cilët numërojnë në sa mënyra mund të zgjedhen k elemente nga bashkësia me n elemente janë shembull i relacioneve rekurente shumëdimensionale. Për t'i shprehur këta koeficientë në formë rekursive përdoret Identiteti i Paskalit



me kushtet fillestare:

Me këto formula gjenerohet vargu i pafundëm i njohur si Trekëndëshi i Paskalit. Këta terma gjenden edhe me formulën:

 Zgjidhja e relacioneve rekurente homogjene 
Jo të gjitha relacionet rekurente mund të zgjidhen, por në vijim po shqyrtojmë rastet që mund të zgjidhen me metodën e zevendësimit dhe metodën e koeficientëve konstantë - ekuacionit karakteristik.

 Zgjidhja me metodën e zëvendësimit 
Metoda më e thjeshtë e zgjidhjes së relacioneve rekurente është metoda e zëvendësimit. Fillimihst e zëvendësojmë vlerën e  në ekuacionin e dhënë, pastaj vlerën e , , etj. Dhe kështu, tek relacionet rekurente të rendit të parë do të mund të vërejmë një ekuacion i cili më pas duhet të vërtetohet, p.sh. me anë të iduksionit matematik.

Kjo metodë funksionon mirë vetëm për relacionet e rendit të parë, dhe për disa relacione të rendit të dytë.

 Zgjidhja me anë të ekuacionit karakteristik kur rrënjët janë të ndryshme 
Le të jenë  numra realë. Supozojmë se ekuacioni karakteristik 

ka  rrenje . Atëherë vargu  është zgjidhje e relacionit rekurent

atëherë dhe vetëm atëherë kur 

për    ku  janë konstante.

 Zgjidhja me anë të ekuacionit karakteristik kur rrënjët mund të mos jenë të gjitha të ndryshme 

Le të jenë  numra realë. Supozoni se ekuacioni karakteristik

ka  rrënjë të ndryshme  me shumëfisha , përkatësisht, pra që  për  dhe .  Atëherë një varg  është një zgjidhje e relacionit rekurent

nëse dhe vetëm nëse

për  ku  janë konstante për  dhe .

 Zgjidhja e relacioneve rekurente johomogjene 
Rikujtojmë se relacioni rekurent johomogjen kishte formën:

ku  janë numra realë dhe  është funksion jo-zero i cili varet vetëm nga n.

Shënojmë  pjesën homogjene të relacionit dhe  pjesën partikulare. Atëherë çdo zgjidhje e rekurencës do të jetë e formës .

Nëse  mund t'a shënojmë në formën:

ku  janë numra realë dallojmë dy raste: 

 Nëse  nuk është zgjidhje e ekuacionit karakteristik të pjesës homogjene atëherë një zgjidhje partikulare merret:

.

 Nëse  është zgjidhje e -fishtë e ekuacionit karakteristik të pjesës homogjene, atëherë një zgjidhje partikulare merret:

.

 Aplikimi 

 Biologji 
alt=Shtimi i popullatës së lepujve sipas vargut të Fibonaçit|parapamje|Shtimi i popullatës së lepujve sipas vargut të Fibonaçit
alt=Algoritmi i kërkimit binar|parapamje|Algoritmi i kërkimit binar
Disa nga relacionet më të njohura të rekuerencës e kanë origjinën në përpjekjet për të modeluar dinamikën erritjes së  popullsisë. Për shembull, numrat e Fibonaçit dikur u përdorën si model për rritjen e një popullate lepujsh.Madje, relacionet rekurente shpesh përdoren për të modeluar ndërveprimin e dy ose më shumë popullatave. Për shembull, modeli Nicholson-Bailey për një ndërveprim organizëm-parazit jepet nga

ku   përfaqëson organizmat e infektuar, dhe   parazitët, në kohën  .

 Shkenca kompjuterike 
Relacionet rekurente janë gjithashtu të një rëndësie themelore në analizën e algoritmeve. Nëse një algoritëm është projektuar në mënyrë që të ndajë një problem në nënprobleme më të vogla (përçaj dhe sundo), koha e ekzekutimit të tij përshkruhet nga një relacion rekurent.

Një shembull i thjeshtë është koha që i duhet një algoritmi për të gjetur një element në një varg të renditur me   elementë, në rastin më të keq.

Një algoritëm naiv do të kërkojë nga e majta në të djathtë, një element në të njëjtën kohë. Skenari më i keq i mundshëm është kur elementi i kërkuar është i fundit, kështu që numri i krahasimeve është  .

Një algoritëm më i mirë është algoritmi i kërkimit binar. Megjithatë, ai kërkon një varg të renditur. Së pari do të kontrollojë nëse elementi është në mes të vargut. Nëse jo, atëherë do të kontrollojë nëse elementi i mesëm është më i madh apo më i vogël se elementi i kërkuar. Në këtë pikë, gjysma e vargut mund të hidhet poshtë dhe algoritmi mund të ekzekutohet përsëri në gjysmën tjetër. Numri i krahasimeve do të jepet nga relacioni rekurent


kompleksiteti kohor i të cilit do të jetë  .

__INDEX__