Izpitno vprašanje DIRI2005 2200

Iz MaFiRaWiki

Vprašanje

Rekurzija: primer, razlaga, značilnosti.

Odgovor

REKURZIJA je ena od osnovnih algoritemskih tehnik v programiranju. Metoda, ki kliče sama sebe, je rekurzivna metoda. Taka metoda ne sme klicati samo sebe v vsakem izvajanju, ker se potem izvajanje metode nikoli ne ustavi (najpogostejša napaka pri pisanju rekurzivnih metod). Zelo pomembno pri programiranju rekurzivne metode je postaviti ustavitveni pogoj, da se rekurzivni klici ustavijo. Ustavitveni pogoj pa je zelo majhen oziroma enostaven problem. Bistvo rekurzije je v tem, da izvajamo postopek, ki vodi do rešitve problema, na vedno manjšem obsegu podatkov. Ker pri rekurziji metoda kliče samega sebe, se vedno začne s pogojem (if), ki ustavi rekurzijo.

Primer:

  1.  
  2. public clas Faktoriela
  3. {
  4. public static int fakt(int n)
  5. {
  6. if (n == 0)
  7. {
  8. return 1;
  9. }
  10. else
  11. {
  12. return n * fakt(n - 1);
  13. }
  14. }
  15.  
  16. public static void main(String[] args)
  17. {
  18. int dokam = 4;
  19. int k = 1;
  20. while (k <= dokam)
  21. {
  22. System.out.println(k + "! = " + fakt(k));
  23. k++;
  24. }
  25. }

Razlaga:

Definicija: n! = n * (n-1)*(n-2)*…*3*2*1
Rekurzivna definicija: n! = n * (n-1)!

Rekurzivna metoda:

  1.  
  2. public static int fakt(int n)
  3. {
  4. if (n == 0) //ustavitveni pogoj
  5. {
  6. return 1;
  7. }
  8. else
  9. {
  10. return n * fakt(n - 1);//klic metode v metodi
  11. }
  12. }

Kako se izvaja metoda?

n! bomo torej lahko izračunali, če bomo poznali (n-1)!. Če je n = 0, je rezultat 1(to je ustavitveni pogoj) sicer pa je rezultat = n * fakt(n – 1) (klic metode na manjšem obsegu podatkov)

  • 4! Lahko izračunamo, če poznamo 3!: 4! = 4 * 3!
    3! Lahko izračunamo, če poznamo 2!: 3! = 3 * 2!
    2! Lahko izračunamo če poznamo 1!: 2! = 2 * 1!
    1! Lahko izračunamo, če poznamo 0!: 1! = 1 * 0! , če ne bi bilo ustavitvenega pogoja , bi se metoda izvajala v neskončnost:
    0! = 0 * (-1)!, (-1)! = (-1) * (-2)!,….


  • 20! = 1 postavimo za ustavitveni pogoj in ko zvemo, da je 0! = 1 lahko v obratnem vrstnem redu računamo 4!:
    1! = 1 * 0! = 1 *1 = 1
    2! = 2 * 1! = 2 *1 = 2
    3! = 3 * 2! = 3 *2 = 6
    4! = 4 * 3! = 4 *6 = 24
Osebna orodja