Živel je mož, imel je psa, lepo ga je učil.
Nekoč ukradel mu je kos mesa, zato ga je ubil.
Postavil mu je spomenik in nanj napisal:
CSharp - Rekurzija
CSharp - Rekurzija
Matija Lokar
Pesmica
Zgodba
Bila je temna, nevihtna noč ... Ladjo so valovi premetavali naprej in nazaj, veter je zavijal med jadri in dež se je zlival na palubo. Posadka je bila zbrana ob petrolejki. Vsi so se zavijali v odeje in trepetali, ko je kapitan pričel pripovedovati zgodbo:
"Bila je temna, nevihtna noč ..."
Slika v sliki
Problemi
Problemi
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.
Problemi
- Izračunaj s čim manj množenji.
- Hanoiski stolpiči
Rekurzija
- Različni problemi
Naloga:
- Sestavi navodila (postopek), s katerim bi problem rešil
Navkljub različnosti:
- Skupni prijem: rekurzija
Rekurzija
V Slovarju slovenskega knjižnega jezika SSKJ ni besede rekurzija, pojavlja pa se beseda
- rekurz -a m (u) knjiž. vrnitev (na kako stvar, dejstvo): rekurz na že omenjana dognanja ni potreben / v njegovih romanih so pogosti rekurzi v preteklost (tudi v filmih je tega precej)
- rekurirati -am dov. in nedov. (i) knjiž. vrniti se (na kako stvar, dejstvo): pogosto rekurirati na nekatera dejstva, spoznanja
Rekurzija
V Velikem slovarju tujk je dana definicija rekurzije (iz latinščine recurrere iti nazaj, vrniti se):
- definiranje funkcije ali postopka s samim seboj (informatika)
- izvajanje veličine ali funkcije, ki jo je treba šele definirati na že znano veličino (matematika). Označuje tudi zaporedje, katerega n-ti člen je določen z enim ali več predhodnimi členi.
Rekurzija
- Tudi v vsakdanjem življenju srečamo rekurzijo.
Definicija prednika neke osebe je lahko:
- prednik osebe je eden od roditeljev osebe (osnovni primer)
- prednik pa je tudi tudi roditelj kateregakoli prednika (rekurzivni primer)
Rekurzija
|
Rekurzija
Po računalniško:
- Postopek, ki je definiran (določen, opisan) sam s sabo.
Rekurzija
- 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 kot npr. pri pesmici
ustavitveni pogoj:
- Kdaj v postopku ne uporabimo istega postopka
- Običajno: ko je problem "majhen" (enostaven)
Faktoriela
Zelo hitro naraščajoča zadeva
- Rekurzivna definicija:
- bomo izračunali, če bomo poznali
3! = 3 * 2!
- 2! = 2 * 1! =
- 1! = 1 * 0! =
- 0! = 0 * (-1)! = ???
- 0! = 1
Faktoriela - postopek
Faktoriela(n):
Če je n = 0, je rezultat 1
sicer pa
rezultat = n * faktoriela(n – 1)
Če je n = 0, je rezultat 1
sicer pa
rezultat = n * faktoriela(n – 1)
Faktoriela
- ali
public static int Faktoriela(int n) {
if (n == 0) return 1;
else return n * Faktoriela(n-1);
}
System.Console.WriteLine("4! = " + Faktoriela(4));
if (n == 0) return 1;
else return n * Faktoriela(n-1);
}
System.Console.WriteLine("4! = " + Faktoriela(4));
Faktoriela
|
- je potenca števila 2 (denimo 16)
- .... 15 množenj
- .................... 4 množenja
- Kaj pa, če npr.14
- ......... 5 množenj
if (n == 2) return y * y;
else {
pom = Pot(y, n / 2);
return pom * pom;
}
else {
pom = Pot(y, n / 2);
return pom * pom;
}
- če ni potenca 2
if (n == 1) return y;
else {
pom = Pot(y, n / 2);
if (n % 2 == 0){
return pom * pom;
}
else {
return y * pom * pom;
}
}
else {
pom = Pot(y, n / 2);
if (n % 2 == 0){
return pom * pom;
}
else {
return y * pom * pom;
}
}
Kaj je torej rekurzija
- Kako je v slovarju definirana beseda 'rekurzivno' ?
- Piše: Glej 'rekurzivno'.
Hanoiski stolpiči
Problem Hanoiskih stolpičev:
|
| |
|
|
Hanoiski stolpiči
Hanoiski stolpiči - prikaz
Hanoiski stolpiči - ideja
|
Hanoiski stolpiči - ideja
- Daj obroč z A na C
- Prestavi n –1 obročev z B na C (s pomočjo A)
Hanoiski stolpiči
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 ?
Hanoiski stolpiči
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
Hanoiski stolpiči
/* n obročev z A na C s pomočjo B */
Hanoi(n, A, B, C)
Če je n = 1 potem daj obroč z A na C
sicer pa
Hanoi(n-1, A, C, B)
Daj obroč z A na C
Hanoi(n-1, B, A, C)
Hanoi(n, A, B, C)
Če je n = 1 potem daj obroč z A na C
sicer pa
Hanoi(n-1, A, C, B)
Daj obroč z A na C
Hanoi(n-1, B, A, C)
Hanoiski stolpiči
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);
}
}
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);
}
}
- Pesmica
- Zgodba
- Slika v sliki
- Problemi
- Problemi
- Problemi
- Rekurzija
- Rekurzija
- Rekurzija
- Rekurzija
- Rekurzija
- Rekurzija
- Rekurzija
- Faktoriela
- Faktoriela - postopek
- Faktoriela
- Faktoriela
- Kaj je torej rekurzija
- Hanoiski stolpiči
- Hanoiski stolpiči
- Hanoiski stolpiči - prikaz
- Hanoiski stolpiči - ideja
- Hanoiski stolpiči - ideja
- Hanoiski stolpiči
- Hanoiski stolpiči
- Hanoiski stolpiči
- Hanoiski stolpiči
