Zoran Skoda rekurzija

Rekurzija je jedan od načina definiranja, a ponekad i način računanja veličina ili funkcija koje zavise od parametra koji je prirodan broj. Parametar je dodatni objekt (najčešće veličina) o kojem zavisi razmatrana veličina. Npr. temperatura nekog mjesta u neko vreme ima smisla ako kažemo koje je mjesto i koje je vrijeme, pa su dakle mjesto i vrijeme parametri potrebni za određivanje te temperature.

Kažemo da je niz veličina $A_n$ (koje zavise od parametra $n\in\mathbb{N}$) definirana rekurzivno ako je zadan $A_n$ za $n = 1$ (ili, općenitije, popisom za prvih nekoliko vrijednosti prirodnih brojeva, recimo $A_1, A_2$ i $A_3$) i ako je zadano pravilo rekurzije kako se $A_{n+1}$, počevši barem od prvog broja koji nije dan popisom, definira uz pomoć vrijednosti $A_n$ (ili općenitije “nižih” vrijednosti $A_m$ za $m\leq n$). Slično možemo rekurzijom definirati i veličine koje zavise od nekoliko prirodnih brojeva kao parametara ili kad parametar kreće od $0$, tj. $n\in \mathbb{N}_0$.

Primjeri rekurzivnih definicija

Primjer. Množenje prirodnih brojeva dano je rekurzivno po drugoj varijabli pomoću zbrajanja pravilom

• $m\cdot 1 = m$ (baza definicije po rekurziji)

• $m\cdot (n+1) = m\cdot n + m$ (rekurzija ili rekurzivna relacija)

Tako je npr. $3\cdot 3 = 3\cdot 2 + 3$ jer je $3 = 2 + 1$, pa u rekurziji uzmemo $n = 2$. Dalje, $3\cdot 2 = 3\cdot 1 +3$, pa je dakle $3\cdot 3 = 3\cdot 2 + 3 = ((3\cdot 1)+3) + 3 = (3+3)+3 = 6+3 = 9$.

Alternativno, množenje prirodnih brojeva može se zadati rekurzijom po prvoj varijabli $m$:

$1\cdot n = n$ i $(m+1)\cdot n = m\cdot n + n$.

Propozicija. Te dvije definicije množenja su ekvivalentne.

Dokaz. To ćemo dokazati preko principa matematičke indukcije po broju $N = m+n-1\geq 1$. Prvo množenje ćemo označavati s $\cdot_1$, a drugo s $\cdot_2$. Ako je $N = 1$ tada su $m=n=1$ tj. $1\cdot 1$, a to je $1$ po bazama obje rekurzije. Dakle, neka vrijedi tvrdnja za $N$, moramo dokazati da vrijedi za $N+1$. Neka su brojevi $m$ i $n$ takvi da je $m+n-1$ jednak $N+1$. Sada moramo provjeriti tri slučaja.

Recimo da je $m\geq n\geq 2$. Tada je $m\cdot_2 n = (m-1)\cdot_2 n + n = (m-1)\cdot_1 n + n = ((m-1)\cdot_1 (n-1) + (m-1))+n = ((m-1)\cdot_2 (n-1) + n-1) + m = m\cdot_2 (n-1) + m = m\cdot_1 (n-1) +m = m\cdot_1 n$, pri čemu smo nekoliko puta koristili pretpostavku indukcije za $N$ i $N-1$. Ostali slučajevi su ovome simetrični slučaj $n\geq m \geq 2$ i slučaj kad je barem jedan od brojeva $1$ koji je ostavljen čitatelju.

Korolar. Množenje prirodnih brojeva dano gornjim rekurzijama je komutativno.

Primjer. Funkcija $n!$ (čitamo en faktorijela) je dana na slijedeći način: $1! = 1$ i dok je $(n-1)!$ definirano, stavimo $n! = n\cdot (n-1)!$. Npr. $5! = 5\cdot 4! = 5 \cdot 4\cdot 3! = 5\cdot 4\cdot 3\cdot 2! = 5\cdot 4\cdot 3\cdot 2\cdot 1 = 120$.

Primjer. Fibonaccijevi brojevi. Prva dva Fibonaccijeva broja su $F(1) = 1$ i $F(2) = 1$. Tada rekurzija $F(n+1) = F(n) + F(n-1)$, za $n = 2,3,\ldots$ definira $(n+1)$-i Fibonaccijev broj $F(n+1)$ pomoću po dva prethodnika. Tako konstruiramo Fibonnacijev niz $1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,\ldots$.

category: zadarmat1, zadarmat4