Sveuˇ
ciliˇ
ste J.J. Strossmayera u Osijeku
Odjel za matematiku
Sveuˇ
ciliˇ
sni preddiplomski studij
matematike
Ivana Oreˇski
REKURZIJE
Zavrˇsni rad
Osijek, 2011.
Sveuˇ
ciliˇ
ste J.J. Strossmayera u Osijeku
Odjel za matematiku
Sveuˇ
ciliˇ
sni preddiplomski studij
matematike
Ivana Oreˇski
REKURZIJE
Zavrˇsni rad
Voditelj:
prof. dr. sc. A. Klobuˇ
car
Osijek, 2011.
Recursion occurs when a function (procedure) calls itself directly or indirectly. Often in the
analysis of some (recursive) algorithm algorithms “ divide and conquer ” are reported, they
recursively breaking the problem into two or more subproblems of the same type, as long
as these do become so easy that it can be solved directly. Recursively defined mathematical
objects are also fractals, which shows similarities to himself.
Keywords:
recursion (recursive relations), mathematical induction, recursive problems,
similarity, characteristic equation, linear homogeneous recursion with constant coefficients
- various and multiple roots, non-homogeneous linear recursion with constant coefficients,
nonlinear recursion, recursion systems, methods of “ divide and conquer ”.
Sadrˇ
zaj
1. Uvod
1
2. Op´
cenito o rekurzijama
2
2.1. Rekurzije i matematiˇ
cka indukcija . . . . . . . . . . . . . . . . . . . . . . . .
2
2.2. Jednostavni primjeri rekurzija . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2.1. Hanojske kule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2.2. Fibonaccijevi brojevi . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3. Linearne rekurzije
11
3.1. Linearne homogene rekurzije s konstantnim koeficijentima
. . . . . . . . . .
11
3.1.1. Postupak za rjeˇsavanje linearnih homogenih rekurzija s konstantnim
koeficijentima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.1.2. Razliˇ
citi korijeni
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3.1.3. Viˇsestruki korijeni
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
3.2. Linearne nehomogene rekurzije s konstantnim koeficijentima . . . . . . . . .
16
3.2.1. Postupak za rjeˇsavanje linearnih nehomogenih rekurzija s konstantnim
koeficijentima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
4. Sustavi rekurzija i nelinearne rekurzije
18
5. Rekurzivne relacije za neke kombinatorne brojeve
21
5.1. Catalanovi brojevi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
5.1.1. Problem triangulacije konveksnog
n
-terokuta
. . . . . . . . . . . . .
21
5.1.2. Problem zagrada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
5.2. Bellov i Stirlingov broj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
5.3. Dvoindeksne rekurzije
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
6. Rekurzije u programiranju
25
6.1. Podijeli pa vladaj (Devide and Conquer) . . . . . . . . . . . . . . . . . . . .
28
6.1.1. Merge Sort (sortiranje saˇ
zimanjem) . . . . . . . . . . . . . . . . . . .
29
6.1.2. Quick Sort (brzo sortiranje) . . . . . . . . . . . . . . . . . . . . . . .
29
7. Rekurzija u slikama
30
Literatura
32
2
2.
Op´
cenito o rekurzijama
Rekurzija je u matematici i raˇ
cunarstvu metoda definiranja funkcija u kojima se defini-
raju´
ca funkcija primjenjuje unutar definicije. Rekurzija konstruira klasu objekata ili metoda
(ili objekata iz odredene klase) definiranjem nekoliko jednostavnih osnovnih sluˇ
cajeva ili
metoda (ˇ
cesto samo jednu), i potom definiranjem pravila za razbijanje sloˇ
zenih sluˇ
cajeva u
jednostavnije. Primjerice, rekurzivna definicija predaka osobe je:
•
Neˇ
ciji roditelji su njegovi pretci (
osnovni sluˇ
caj
);
•
Roditelji bilo kojeg pretka su takoder pretci osobe koju promatramo (
korak rekurzije
).
Zgodno je zamisliti da rekurzivna definicija definira objekte u terminima “prethodno defini-
ranih” objekata definiraju´
ce klase. Definicije poput ove su ˇ
ceste u matematici.
Neka je definiran niz brojeva (
a
n
). Tada
rekurzivnom relacijom(rekurzivnom for-
mulom ili rekurzijom)
zovemo svaku relaciju (ˇ
cesto formulu), pomo´
cu koje se
n
-ti ˇ
clan
niza
a
n
izraˇ
zava pomo´
cu nekoliko prethodnih ˇ
clanova
a
k
,
k < n
. Rekurzivna relacija moˇ
ze
elemente niza izraˇ
zavati uvijek pomo´
cu fiksnog broja prethodnika (za neki fiksni
k
∈
N
proizvoljni element niza
a
n
izraˇ
zava pomo´
cu
a
n
−
1
, . . . , a
n
−
k
) ili pomo´
cu svih njegovih pret-
hodnika. U prvom sluˇ
caju govorimo o rekurzivnim relacijama konaˇ
cne, a u drugom o re-
kurzivnim relacijama beskonaˇ
cne proˇslosti. Potrebno je imati poˇ
cetne uvjete (vrijednosti
elemenata niza za neke vrijednosti indeksa) da bi se rekurzivna relacija mogla koristiti za
raˇ
cunanje elemenata niza. Najˇ
ceˇs´
ce su to prvi elementi niza. Za rekurzivne relacije konaˇ
cne
proˇslosti obiˇ
cno uzimamo prvih
k
vrijednosti niza, npr.
a
1
, a
2
, . . . , a
k
, a za beskonaˇ
cne
proˇslosti prvi element niza. Poˇ
cetni uvjeti se ili zadaju ili su dostupni jednostavnim raˇ
cunom.
2.1.
Rekurzije i matematiˇ
cka indukcija
Princip definicije indukcijom
(ili
rekurzijom
) Neka je
S
skup,
a
∈
S
, te neka je za
svako
n
∈
N
dano neko preslikavanje
f
n
:
S
×
S
×
. . .
×
S
→
S
. Tada postoji jedinstveni niz
(
x
n
) u
S
, takav da je
x
1
=
a
x
n
+1
=
f
n
(
x
1
, x
2
, . . . , x
n
)
,
za svako
n
∈
N
.
(1)
Posebno, ako
f
n
ovisi samo o varijabli
x
n
, tj. ako je
f
n
(
x
1
, x
2
, . . . , x
n
) =
f
n
(
x
n
), onda za-
pravo imamo za svako
n
∈
N
preslikavanje
f
n
:
S
→
S
, pa postoji jedinstven niz
x
1
, x
2
, . . . , x
n
, . . .
u
S
, takav da je
x
1
=
a
i
x
n
+1
=
f
n
(
x
n
), za svako
n
∈
N
. Formula (1) se zove
rekurzivna
formula
(ili
relacija
) za niz (
x
n
).
Definicija 2.1.
Neprazan skup
N
zove se skup prirodnih brojeva, a njegovi elementi prirodni
brojevi ako vrijede sljede´
ci Peanovi aksiomi:
P1) Postoji funkcija sljedbenika
s
:
N
→
N
;
P2) Postoji barem jedan element
1
∈
N
takav da je
s
(
n
)
6
= 1
,
∀
n
∈
N
;
P3) Ako je
s
(
m
) =
s
(
n
)
za
m, n
∈
N
onda je
m
=
n
;
