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 nA_n (koje zavise od parametra nn\in\mathbb{N}) definirana rekurzivno ako je zadan A nA_n za n=1n = 1 (ili, općenitije, popisom za prvih nekoliko vrijednosti prirodnih brojeva, recimo A 1,A 2A_1, A_2 i A 3A_3) i ako je zadano pravilo rekurzije kako se A n+1A_{n+1}, počevši barem od prvog broja koji nije dan popisom, definira uz pomoć vrijednosti A nA_n (ili općenitije “nižih” vrijednosti A mA_m za mnm\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 00, tj. n 0n\in \mathbb{N}_0.

Primjeri rekurzivnih definicija

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

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

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

Tako je npr. 33=32+33\cdot 3 = 3\cdot 2 + 3 jer je 3=2+13 = 2 + 1, pa u rekurziji uzmemo n=2n = 2. Dalje, 32=31+33\cdot 2 = 3\cdot 1 +3, pa je dakle 33=32+3=((31)+3)+3=(3+3)+3=6+3=93\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 mm:

1n=n1\cdot n = n i (m+1)n=mn+n(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+n11N = m+n-1\geq 1. Prvo množenje ćemo označavati s 1\cdot_1, a drugo s 2\cdot_2. Ako je N=1N = 1 tada su m=n=1m=n=1 tj. 111\cdot 1, a to je 11 po bazama obje rekurzije. Dakle, neka vrijedi tvrdnja za NN, moramo dokazati da vrijedi za N+1N+1. Neka su brojevi mm i nn takvi da je m+n1m+n-1 jednak N+1N+1. Sada moramo provjeriti tri slučaja.

Recimo da je mn2m\geq n\geq 2. Tada je m 2n=(m1) 2n+n=(m1) 1n+n=((m1) 1(n1)+(m1))+n=((m1) 2(n1)+n1)+m=m 2(n1)+m=m 1(n1)+m=m 1nm\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 NN i N1N-1. Ostali slučajevi su ovome simetrični slučaj nm2n\geq m \geq 2 i slučaj kad je barem jedan od brojeva 11 koji je ostavljen čitatelju.

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

Primjer. Funkcija n!n! (čitamo en faktorijela) je dana na slijedeći način: 1!=11! = 1 i dok je (n1)!(n-1)! definirano, stavimo n!=n(n1)!n! = n\cdot (n-1)!. Npr. 5!=54!=543!=5432!=54321=1205! = 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)=1F(1) = 1 i F(2)=1F(2) = 1. Tada rekurzija F(n+1)=F(n)+F(n1)F(n+1) = F(n) + F(n-1), za n=2,3,n = 2,3,\ldots definira (n+1)(n+1)-i Fibonaccijev broj F(n+1)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,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

Last revised on February 5, 2018 at 19:17:15. See the history of this page for a list of all contributions to it.