Rekurzija

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu
Визуелни облик рекурзије познат као Дросте ефекат.

Рекурзија (лат. recursio, recursion od recurrere: vraćanje) u matematici i informatici označava postupak ili funkciju koji u svojoj definiciji koriste sami sebe. Drugim rečima, ukoliko neki postupak zahteva da delovi problema koje je razdvojio od drugih bivaju nezavisno podvrgnuti istom tom postupku, taj postupak je rekurzivan.

Formalne definicije rekurzije[uredi]

U matematici i računarstvu, rekurzija određuje (gradi) klasu objekata ili metoda (ili objekat iz određene klase) definisanjem nekoliko jednostavnih baznih slučajeva ili metoda (često samo jedan), i definisanjem pravila kako se složeniji slučajevi svode na jednostavnije.

Na primer, sledi rekurzivna definicija predaka date osobe:

  • Roditelji osobe su mu preci (bazni slučaj);
  • Roditelji predaka su takođe preci osobe (korak rekurzije ).

Zgodno je smatrati da rekurzivna definicija definiše objekte u odnosu na prethodno definisane objekte klase koja se definiše.

Definicije poput ove se često javljaju u matematici. Na primer, formalna definicija prirodnog broja u teoriji skupova je: 1 je prirodan broj, i svaki prirodan broj ima svog naslednika, koji je takođe prirodan broj.

Sledi još jedan, možda jednostavniji način da se razumeju rekurzivni procesi:

  1. Da li imaš rešenje? Ako imaš, javi rezultat. (Bez ovakvog uslova za prekidanje, rekurzija bi se vrtela beskonačno).
  2. Ako ne, pojednostavi problem, reši jednostavniji problem (probleme), i spoj rezultate u rešenje početnog problema. Zatim javi rezultat.

Šaljiva ilustracija glasi Kako bi razumeo rekurziju, čovek prvo mora da razume rekurziju. Ili možda tačnije, od Endrua Plotkina: Ako već znaš šta je rekurzija, zapamti odgovor. Ako ne znaš, nađi nekoga ko stoji bliže Daglasu Hofštateru[1], i pitaj njega šta je rekurzija.

Primeri matematičkih objekata koji se često definišu rekurzivno su funkcije, skupovi, i posebno fraktali.

Rekurzivne definicije u matematici[uredi]

Rekurzivne definicije su prisutne u matematici. Primer je sledeća definicija prirodnih brojeva:

  • 1 je prirodni broj
  • Ako je n prirodni broj, onda je to i n+1.

Rekurzijom se definiše i Fibonačijev niz:

  • 1. član niza je 0
  • 2. član niza je 1
  • svaki n-ti član niza (n>2) je suma prethodna dva člana ()

Rekurzivni algoritmi u programiranju[uredi]

Bitno je napomenuti da u savremenim programskim jezicima poput C/C++ i Jave svako rekurzivno rešenje nekog problema ima i svoj iterativni ekvivalent, tj. algoritam koji isti problem rešava bez rekurzije. U praktičnom programiranju uglavnom treba izbegavati rekurziju jer takva rešenja u opštem slučaju troše više vremena od iterativnih.[traži se izvor]

Sledi par primera problema koji su rešeni rekurzijom.

Vrednost faktorijela[uredi]

Faktorijel je matematička funkcija koja se u edukativne svrhe često spominje u kontekstu rekurzije. Faktorijel prirodnog broja n je proizvod njega samog i svih prirodnih brojeva koji su manji od njega:

Pri ovome važe zakoni komutativnosti množenja nad skupom prirodnih brojeva, te se isto može obavljati u bilo kom redosledu. Može se početi od broja n pa ići unazad sve do broja 1. Evo kako bi to izgledalo u programskom jeziku C:

int fakt(int n)
{
	if(n < 2) // Уколико је добијени број мањи од два,
	{ return 1; } // вратити 1.

	else // У супротном,
	{ return n*fakt(n-1); } // вратити тренутни број помножен са
                                 // факторијелом броја за један мањег
                                 // од њега.
}

U konkretnom slučaju ukoliko bi funkcija kao argument dobila broj 5, račun bi se razvijao na način pokazan ispod. Pritom će rekurzivni pozivi funkcija biti obeleženi zagradama, da bi se dočarao redosled početaka i završetaka ovih funkcija.

fakt(5) = 5 · fakt(4)
        = 5 · (4 · fakt(3))             // (јер је fakt(4) = 4 · fakt(3))
        = 5 · (4 · (3 · fakt(2)))       // (јер је fakt(3) = 3 · fakt(2))
        = 5 · (4 · (3 · (2 · fakt(1)))) // (јер је fakt(2) = 2 · fakt(1))
        = 5 · (4 · (3 · (2 · 1)))       // (јер је fakt(1) = 1)

        = 5 · (4 · (3 · (2 · 1)))       // сада се множење ових вредности врши редом
        = 5 · (4 · (3 · 2))             // којим се ф-је завршавају тј. уназад
        = 5 · (4 · 6)
        = 5 · 24
        = 120

Suma niza koji se završava nulom[uredi]

Recimo da je dat niz celih brojeva čiju ukupnu sumu treba odrediti. Jedno rekurzivno rešenje je da se funkciji daje sam niz i indeks od koga treba početi ili nastaviti sabiranje, sve dok se ne dođe do kraja niza. Do tada se prethodno nađene vrednosti akumuliraju na sličan način kao što je to gore prikazano, napredujući za po jedan element prilikom svakog rekurzivnog poziva. Evo kako bi ovaj algoritam bio realizovan u Javi:

public static int sum(int[] niz, int indeks) {
  if(indeks >= niz.length) {                  // Уколико се дошло до краја низа,
    return 0;                                 // рекурзија се прекида и враћа се
  }                                           // нула која представља неутрал за
                                              // операцију сабирања.

  return niz[indeks] + sum(niz, indeks+1);    // У супротном, враћа се сума елемента
                                              // који се налази на датом индексу и
                                              // рекурзивног позива ове функције који
                                              // треба да израчуна суму свих елемената
                                              // након њега
}

Pri čemu se funkcija uvek poziva sa nizom kao prvim argumentom i nulom kao početnim indeksom niza.

Uzevši da je dati niz na primer a = {11,12,13,14,15}, ova funkcija bi račun obavila na sledeći način:

sum(a,0) = a[0] + sum(a,0+1)
         = 11   + (a[1] + sum(a,1+1))
         = 11   + (12   + (a[2] + sum(a,2+1)))
         = 11   + (12   + (13   + (a[3] + sum(a,3+1))))
         = 11   + (12   + (13   + (14   + (a[4] + sum(a,4+1)))))
         = 11   + (12   + (13   + (14   + (15   + 0))))          // нема a[5], враћа се нула

         = 11   + (12   + (13   + (14   + 15)))
         = 11   + (12   + (13   + 29))
         = 11   + (12   + 42)
         = 11   + 54
         = 65

Ovaj problem ima i drugo rešenje. Aritmetika pokazivača u jeziku C omogućava malo drugačiji pristup. Naime, funkcija ovde ne mora da prima i niz, i indeks elementa da bi pristupila elementu. Dovoljno joj je samo dati pokazivač na traženi element. Kako se ovde uvek traži sledeći element, pokazivač na njega je lako dobiti iz pokazivača na trenutni. Da bi se implementacija pojednostavila, uzećemo dodatni uslov da se niz završava sa nulom.

int asum(const int* p)
{
	if(*p == 0) // Уколико је тренутно обрађивани број нула,
	{ return 0; } // рекурзија се прекида. Претходном резултату
                                    // ће бити додата враћена нула.

	else // У супротном, 
	{ return *p + asum(p+1); } // се исти број сабира са следећим и као такав
                                    // враћа претходним сабирцима.
}

Ponašanje ove funkcije je identično ponašanju gorenavedene, s tom razlikom što zadati niz treba da bude a = {11,12,13,14,15,0}. Argumenat pri prvom pozivu funkcije je uvek ime niza, npr. poziv za niz a bi bio asum(a).

Neophodnost nule na kraju niza se može izbeći davanjem dužine niza funkciji.

Verižni razlomci[uredi]

Jedan od verižnih razlomaka, koji se vezuje za vrednost broja pi.

U ovom izrazu se razlomci nižu jedan ispod drugog, pri čemu se svaki ugnježdava u deliocu prethodnog. Pritom se mogu izdvojiti dva niza sabirka i deljenika koji pripadaju svakom od njih. Oni bi glasili ovako:

Sabirci: 1, 3, 5, 7, 9, 11, 13, ... = 2n - 1, n = 1, ...
Deljenici: 1, 4, 9, 16, 25, 36, ... = n², n = 1, ...

U oba niza se uočavaju pravila: prvi je niz neparnih brojeva, a drugi niz kvadratna funkcija prirodnih brojeva. Prvi način predstavljanja ovog niza bi dakle bio formiranje ovih razlomaka po njihovim rednim brojevima, iz kojih vrednosti posmatranih elemenata slede. Ono što je bitno primetiti je da se rekurzija ne može širiti u beskonačnost tj. treba je negde prekinuti. S obzirom da sa porastom rednog broja razlomka i brojevi rastu, i to na način koji umanjuje uticaj svakog sledećeg razlomka na celokupni rezultat, rekurzija se može prekinuti nakon određenog rednog broja razlomaka. Pošto se jedan razlomak, kao i svi njegovi sledbenici, mora izbaciti, ostaje da se poslednji zaključi samo sa neparnim brojem, a ostatak razlomaka približno izrazi nulom. Ovo bi na datom primeru izgledalo ovako:

Implementacija ovog rešenja u programskom jeziku C bi izgledala ovako:

double f1(int n) // Функција добија редни број разломка
{
	if(n > 200) // Ако је редни број већи од 200,
	{ return 2*n-1; } // рекурзија се прекида враћањем само 
                                     // одговарајућег непарног броја.

	else // У супротном
	{
		return // се враћа збир
		 (2*n-1) // одговарајућег непарног броја,
		 + n*n / f1(n+1); // и квадрата редног броја разломка,
	} // подељеног са следећим разломком.
}

Ovu funkciju treba uvek pozivati sa argumentom n=1.


Često ima više rešenja. Posmatranjem nizova se može uvideti i sledeća zakonitost, pri istoj raspodeli na razlomke.

Ako su kod jednog razlomka sabirak a i deljenik b, kod sledećeg će to biti a+2 i a+b+2.

Pritom redni broj razlomka, koji je u ovom slučaju n=a+1/2, ne mora biti jedini kriterijum za zaustavljanje rekurzije. Celobrojni tip, koji će i u ovom slučaju biti korišten za obradu vrednosti a i b ima svoja ograničenja u opsegu koji pokriva, tako da bi nekontrolisani rast ovih vrednosti dao pogrešne rezultate ili izazvao pad programa. S obzirom da vrednost b raste mnogo brže od vrednosti a, dovoljno je prekinuti rekurziju kada dođe do neke vrednosti za koju je sigurno da je dostižna pre postizanja nedozvoljenih vrednosti. Kako i nije potrebno previše razlomaka da bi se valjani rezultat smestio u dabl, tip realnih brojeva, ova granica sme biti prilično nisko.

Jedna od mogućih implementacija bi bila:

double f(int a, int b)
{
	if(b > 1000) // Уколико променљива ''b'' премаши унапред
                                        // задату вредност,
	{ return a; } // рекурзија се прекида и враћа се само ''a''.

	else // У супротном, рекурзија се наставља
	{ return a + b/f(a+2,a+b+2); } // и враћа се следећи сабирак бесконачног низа,
                                        // који у себи садржи рекурзивни позив
}

Ova funkcija se uvek mora pozivati sa argumentima a=1 i b=1

Reference[uredi]

  1. ^ Daglas Hofštater je američki akademik koji je napisao čuvenu knjigu Gedel, Ešer, Bah: Večna zlatna pletenica.

Vidi još[uredi]