• Izračunaj volumen telesa, preluknjanega n-krat

• Poišči največje in najmanjše število v tabeli števil
• Uredi podatke po velikosti.
• Izračunaj produkt naravnih števil od 1 do n.

• Različni problemi

• Naloga:

  • Sestavi navodila (postopek), s katerim bi problem rešil

• Navkljub različnosti:

  • Skupni prijem: rekurzija

Po računalniško:

Postopek, ki je definiran (določen, opisan) sam s sabo.

• Rešitev problema – podana s samim problemom, le nad manjšim obsegom podatkov
• V opisu postopka rešitve uporabimo kar ta postopek
• Če želimo priti do rešitve, ne moremo nadaljevati v nedogled

• ustavitveni pogoj:

  • Kdaj v postopku ne uporabimo istega postopka
  • Običajno: ko je problem "majhen" (enostaven)

• Različni problemi

• Naloga:

  • Sestavi navodila (postopek), s katerim bi problem rešil

• Splošni algoritem:

  • Če je problem majhen, vrni rešitev

  • Sicer pa

    • Razdeli problem na manjše podprobleme iste vrste, kot je prvotni problem
    • S klicem istega algoritma (rekurzija) pridobi rešitve vseh podproblemov
    • Združi rešitve podproblemov v enotno rešitev

• 7! = 1 * 2* 3 * 4 * 5 * 6 * 7
• 3! = 6

• Zelo hitro naraščajoča zadeva

  • 3! = 6
  • 5! = 120
  • 42! = 1405006117752879898543142606244511569936384000000000
• Rekurzivna definicija: n! = n * (n-1)!
• n! bomo izračunali, če bomo poznali (n-1)!

• 3! = 3 * 2!

  • 2! = 2 * 1! =
  • 1! = 1 * 0! =
  • 0! = 0 * (-1)! = ???
• 1! = 1

• Faktoriela(n):
• Če je n = 1, je rezultat 1
• sicer pa
• pom = Faktoriela(n – 1)
• rezultat = n * pom

• 1! = 1
• n! = n * (n-1)!

public static int Faktoriela(int n) {
  if (n == 1) return 1;
  else {
    int pom = Faktoriela(n-1);
    return n * pom;
}

Rekurzivno reševanje faktoriele

• n je potenca števila 2 (denimo 16)
• y = y y y y y y y y y y y y y y y y .... 15 množenj
• y = y y
• y = y y
• y = y y
• y = y y
• .................... 4 množenja

• Kaj pa, če n npr.14
• y = y y
• y = yy
• y = y y
• y = y y
• y = y y ......... 5 množenj

if (n == 1) return y;
else {
   pom = Pot(y, n / 2);
   if (n % 2 == 0){
     return pom * pom;
   }
   else {
      return y * pom * pom;
   }
}

Problem Hanoiskih stolpičev:

prestavi n-1 obročev z A na B (s pomočjo C)

Daj obroč z A na C

Prestavi n –1 obročev z B na C (s pomočjo A)

• Preloži n obročev z A na C s pomočjo B

  • Preloži n-1 obročev z A na B s pomočjo C
  • Daj obroč z A na C
  • Preloži n-1 obročev z B na C s pomočjo A

• ustavi ?

Preloži n obročev z A na C s pomočjo B

Če je n = 1 potem daj obroč z A na C

sicer pa

Preloži n-1 obročev z A na B s pomočjo C

Daj obroč z A na C

Preloži n-1 obročev z B na C s pomočjo A

public static void Hanoi(int n, char st1,
         char st2,char st3) {
  if (n == 1)  {
    System.Console.WriteLine("Prelozi z " + st1
      + " na " + st3);
  }
  else   {
    Hanoi(n-1, st1, st3, st2);
    System. Console.WriteLine("Prelozi z " + st1
      + " na " + st3);
    Hanoi(n-1, st2, st1, st3);
  }
}

hanoi(3, "A", "B", "C")
    hanoi(2, "A", "C", "B")
      hanoi(1, "A", "B", "C")
        izpis: Prelozi z A na C
      izpis: Prelozi z A na B
      hanoi(1, "C", "A", "B")
        izpis: Prelozi z C na B
    izpis: Prelozi z A na C
    hanoi(2, "B", "A", "C")
      hanoi(1, "B", "C", "A")
        izpis: Prelozi z B na A
      izpis: Prelozi z B na C
      hanoi(1, "A", "B", "C")
        izpis: Prelozi z A na C