Izpitno vprašanje RAČ2PRA 2200

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka SonjaValenčič.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Predmet Računalništvo 2 (FMF PRA)

Vsebina

Vprašanje

Rekurzija: primer, razlaga, značilnosti

Odgovor

Rekurzivno pomeni nanašajoč se na samega sebe. Pri programiranju poznamo rekurzivne klice metode in rekurzivne definicije podatkovnih struktur.
Rekurzivni programi so primerni v glavnem takrat, ko želimo rešiti problem ali izračunati funkcijo ali obdelati podatkovno strukturo, ki je že definirana rekurzivno.

Rekurzivni klici metod

Rešitev problema lahko izračunamo, če poznamo rešitev podproblema, ki je istega tipa, vendar nad manjšim obsegom podatkov. Rešitev le-tega pa lahko izračunamo, če poznamo rešitev njegovega podproblema, nad še manjšim obsegom podatkov... Metodo kličemo rekurzivno, dokler ni izpolnjen ustavitveni pogoj (sicer se ne bi rekurzivno računanje nikoli končalo). Takrat je problem dovolj majhen in ga rešimo kar direktno.
Znotraj metode imamo ponavadi definirano množico lokalnih spremenljivk, konstant,... Vsakič, ko metodo pokličemo rekurzivno, ustvarimo novo množico lokalnih spremenljivk. Čeprav imajo te ista imena kot ustrezni elementi v množici, ki je nastala pri prejšnjem klicu metode, imajo lahko različne vrednosti. Imena se vedno nanašajo na tisto množico spremenljivk, ki smo jo zgradili nazadnje.
V praksi naj bi bila globina rekurzije razmeroma majhna. Razlog je ta, da vsak rekurzivni klic metode zahteva nekaj dodatnega pomnilniškega prostora za shranjevanje spremenljivk in za zapis trenutnega stanja računalniške enote (to je potrebno zato, da po zaključku novega klica metode lahko nadaljujemo s starim).

Primer: Računanje n-tega člena Fibonaccijevega zaporedja

  1.  
  2. public static int fiboNti(int n) {
  3. if(n == 0 || n == 1) return 1; //ustavitveni pogoj: prva dva člena imata vrednost 1
  4. //metodo kličemo rekurzivno dokler je n >= 2
  5. return fiboNti(n-1) + fiboNti(n-2);
  6. }

Rekurzivna definicija podatkovnih struktur

Primer: Definicija dvojiškega drevesa
Dvojiško drevo je bodisi prazno ali pa ga sestavlja posebej odlikovano vozlišče koren, ki ima levo in desno poddrevo. Levo in desno poddrevo sta spet dvojiški drevesi.

Osebna orodja