ALG9

3.7. Analiza programów rekurencyjnych 69

W tym paragrafie przedstawiona zostanie metoda mająca charakter o wiele ogólniejszy. Ma ona swoje uzasadnienie matematyczne, którego z powodu jego skomplikowania nie będę przedstawiał. Osoby szczególnie zainteresowane stroną matematyczną powinny dotrzeć bez kłopotu do odpowiedniej literatury (patrz uwagi zamieszczone we wstępie rozdziału).

3.7.1.Terminologia

Lektura kilku następnych paragrafów wymaga od nas poznania terminologii, którą będziemy się dość często posługiwać. Pomimo „groźnego” wyglądu, zrozumienie poniższych definicji nie powinno Czytelnikowi sprawić szczególnych kłopotów.

Szereg rekurencyjny liniowy SRL jest to szereg o następującej postaci:

r

x

H+r.wIłO

oznaczenia:

u(n.m) nierekurencyjna reszta równania, będąca wielomianem stopnia m i zmiennej n. Przykładowo:

•    jeśli u(n,m)—3n+1, to mamy wielomian stopnia pierwszego;

•    jeśli u(n,»i)=2, to jest to wielomian stopnia zerowego.

uwagi:

•    współczynniki a, są dowolnymi liczbami rzeczywistymi;

•    r jest liczbą całkowitą.

Skomplikowaną postacią tego wzoru nie należy się przejmować, jest to po prostu sformalizowany zapis ogólnego równania rekurencyjnego, podany raczej gwoli formalności niż w jakimś praktycznym celu.

Równanie charakterystyczne RC jest to wielomian sztucznie stworzony na podstawie równania rekurencyjnego, powstały wg wzoru:

r

Równanie to można rozwiązać, otrzymując rozkład postaci:

r