Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Pomoc oko jednog algoritma koji koristi rekurziju

[es] :: Java :: Pomoc oko jednog algoritma koji koristi rekurziju

[ Pregleda: 2461 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Bond123

Član broj: 330809
Poruke: 22
78.104.151.*



Profil

icon Pomoc oko jednog algoritma koji koristi rekurziju11.11.2015. u 23:11 - pre 102 meseci
Imao sam jedan zadatak, malo vjezbao rekurziju pa nasao par problemcica. I dosao sam do problema da treba izracunati powerN, znaci stepen broja. Metoda se sastoji iz dva parametra (baza, eksponent). Ja sam to nekako intuitivno rijesio, napisao kod, pokusao i nekim slucajem radi. Nije bas da ne znam nikako kako radi, jer sam SAM napisao kod, ne kopirao, ali mi ima jedan ili dva dijela nejasna, pa ako neko moze da mi pojasni ovako prolaz kroz metodu. Radi se o Javi.

Kod je sljedeci :

public int powerN(int base, int n) {
if(n==1){
return base;}
if(n==0){
return 1;}
if(n>1){
return base* powerN(base, n-1);}
return base;
}

Ono sto ne razumijem: 1. prolaz kroz metodu ( za primjer (3,2)) n !=1 to preskace, ide dalje n!=0 ide dalje, n>1 ulazi u if blok i vraca znaci 3 * (ponovo poziva metodu)..2. prolaz kroz metodu za (3,1)..Sad dolazi do problema shvatanja! n je sada jednako 1 i treba da vrati bazu, zar ne? Zasto mi vraca 9, kad uopste nije vise prolazio kroz metodu i nije dosao do onog 3 *.. pa da pise 3 * 3.. Zasto mi ne vrati samo 3? Drago je meni da funkcionise, ali mi nije najjasnije ovo. Stavio sam samo return base, a base ostaje uvijek ista. Kako mi vrati 9 a ne 3? Nikako mi nije jasno kako ide taj zadnji korak metode, pa ako ima neko ko se duze bavi programiranjem da mi ovo malo pojednostavi? Hvala unaprijed!
 
Odgovor na temu

plague
Software Developer
Auckland, NZ

Član broj: 46734
Poruke: 623
*.136.4.181.host.layer2.co.nz.



+373 Profil

icon Re: Pomoc oko jednog algoritma koji koristi rekurziju12.11.2015. u 00:19 - pre 102 meseci
Edit: Tek sada sam skontao da se pitas zasto je rezultat, a ne zasto ti vraca u najdubljoj rekurziji 9.
Svakako, ovaj moj primer ispod ce ti pomoci da razumes kako radi rekurzija.

Poenta je da kada dodje do bazicnog slucaja to nije kraj izvrsavanja, nego tada se stice uslov da se nastavi izvrsavanje prethodne rekuzije.

Kao da ides niz stepenice gde svaka ima vrednost base i ima n stepenica.

Ako krenes od stepenika 6 on ti kaze: Moja vrednost je 3 * vrednost svih preostalih stepenika.
Ti kazes ok, idem na sledeci stepenik da vidim njegovu vrednost.
Kada se spustis na sledeci on ti kaze isto i ti nastavis dalje.
Kada dodjes do zadnjeg stepenika n=1 on ti kaze: Moja vrednost je 3 * prestali... cekaj, nema vise stepenika, moja vrednost je 3!
Zahvalis mu se i krenes da se vracas i stepeniku iznad kazes: Hej, vrednost stepenika ispod je 3!
On ti odgovori: E super, moja vrednost je 3 * 3 = 9
Vratis se opet jedan stepenik i kazes: Hej, vrednost stepenika ispod je 9.
On ti odgovori: E super, moja vrednost je 3 * 9 = 27
Itd..
Kada vise nema stepenika ti si zapravo izasao iz rekurzije i ono sto si izmnozio do tada je rezultat.

---------------------------------------------

Ne vraca 9 nego 3. Mozda u debug modu lose tumacis vrednosti.

Probaj da razdvojis korake:
Code (java):

          if (n == 1) {
               System.out.println(String.format("(%s, %s): %s", base, n, base));
               return base;
          }
          if (n == 0)
               return 1;
          if (n > 1) {
               int recursionResult = powerN(base, n - 1);
               System.out.println(String.format("(%s, %s): %s", base, n, base * recursionResult));
               return base * recursionResult; //nadam se da niko nece cupati kosu jer opet mnozim :P
          }
          throw new IllegalArgumentException("Negative power not supported");
     }


Ovo ce print samo vrednost rekurzivnih poziva, tj nece odstampati prvi poziv.

Primer:

Code:

powerN(3, 6);

-----------

(3, 1): 3
(3, 2): 9
(3, 3): 27
(3, 4): 81
(3, 5): 243
(3, 6): 729


Kao sto vidis rezultat najdublje rekuzije je 3, jedino sto mi pada na pamet je da si u debug modu gledao ceo izraz base * powerN(base, n-1).


[Ovu poruku je menjao plague dana 12.11.2015. u 01:49 GMT+1]
 
Odgovor na temu

Bond123

Član broj: 330809
Poruke: 22
78.104.151.*



Profil

icon Re: Pomoc oko jednog algoritma koji koristi rekurziju12.11.2015. u 18:22 - pre 101 meseci
Ma mozda sam se pogresno izrazio s tim 'vraca', jer nisam profesionalni programer nego ucim, pa mozda ne znam najbolje sta se misli pod kojim izrazom. Mislio sam, zasto mi za n=2 ispise rezultat 9. Odnosno, na koji nacin, kad sam ja svugdje stavio return base; a 'base' je ostalo nepromijenjeno, nigdje nisam napisao base= base * recursionResult(base, n-1) ili slicno. Mozda mi je malo tesko sad da shvatim zasto to tako radi ako nisam mijenjao base a vraca mi drugi rezultat u odnosu na pocetnu inicijalizaciju base-a. Jer do sad sam navikao raditi recimo neke lakse zadatke, s for, while, do while petljama gdje je jasno odredjeno kako sta i kada radi. Znam da se svaki rekurzivni metod moze napisati i pomocu petlji, ali sad ucim rekurziju i pokusavam vecinu pomocu nje pisati kako bi je shvatio. Hvala na objasnjenju, nisam znao da ovo radi ovako sa vracanjem uz stepenice kada se dodje do bazicne vrijednosti :) ;)
 
Odgovor na temu

Milan Milosevic

Član broj: 67
Poruke: 932
*.dynamic.isp.telekom.rs.



+31 Profil

icon Re: Pomoc oko jednog algoritma koji koristi rekurziju13.11.2015. u 05:43 - pre 101 meseci
Napisao si to u liniji

Code:
return base* powerN(base, n-1);}


U ovom delu koda funkcija poziva samu sebe, ali sa smanjenim indeksom stepena za jedan.



Primer za n=3



Ovde jasno mozes da uocis da se ista funkcija stepenovanja poziva 3 puta ali sa tri razlicita argumenta
za n =3, 2, 1.
Tek kada pozove sebe za argument n =1 pocinje da vraca resenja unazad



[Ovu poruku je menjao Milan Milosevic dana 13.11.2015. u 06:57 GMT+1]
 
Odgovor na temu

Bond123

Član broj: 330809
Poruke: 22
78.104.151.*



Profil

icon Re: Pomoc oko jednog algoritma koji koristi rekurziju14.11.2015. u 20:26 - pre 101 meseci
Hvala momci na pomoci i objasnjenjima. Naisao sam na sljedeci problem : ne znam kako da ispisujem rezultate rekurzije. Pokusao sam sa for petljom u glavnoj metodi ali mi, logicno, ne prepoznaje parametar n iz pomocne metode.

Treba mi npr. da ispisuje :

L(0) = 1
L(1) = 1
L(n) = L(n - 1) + L(n - 2) + 1 if n > 1.

Ne znam kako da mi ispisuje ovo korak po korak za L(0), L(1)... meni rekurzijom samo izbacuje konacan rezultat. Ovo je moj kod, metoda je lagana:

private static int recursion(int n){
if(n==0 || n==1){
return 1;
}
else {
return recursion(n-1) + recursion(n-2) +1 ;
}

Gdje da ubacim for petlju ili sta vec da mi ispisuje vrijednost po vrijednost. Imam jos zadataka gdje treba da se trougao iscrta pomocu rekurzije ali mi nije jasno kako da prelazim rekurzijom u nove redove?

Ako imate vremena da ostavite objasnjenje, nadam se da nisam dosadan. Neko ce reci googlaj ali ne mogu ja googlu da objasnim problem i da mu ovako ispricam. Lakse mi je da mi neko objasni ovako, jer pokusavao sam i sam, ne trazim da mi se rijesi.
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
134.90.133.*



+62 Profil

icon Re: Pomoc oko jednog algoritma koji koristi rekurziju15.11.2015. u 10:29 - pre 101 meseci
Mozda ovako nesto:

Code:

private static int recursion(int n){
  if(n==0 || n==1){
  return 1;
  }
  else {
    int temp = recursion(n-1) + recursion(n-2) +1;
    System.out.println("L(" + n + ") = " + temp; 
    return temp;
  }


Vidi da li print() ide bas tako, zaboravlja se polako i java... heh.

Pozz
 
Odgovor na temu

Bond123

Član broj: 330809
Poruke: 22
78.104.151.*



Profil

icon Re: Pomoc oko jednog algoritma koji koristi rekurziju15.11.2015. u 18:37 - pre 101 meseci
Hm.. pocelo je ispisivati u redove kako i treba, ali mi ne mijenja indeks broja L dobro, treba da krene od 0 pa do n.. a meni mijesa nesto (2,2,3,4).. Probacu sam da shvatim. Jedino ako znas u cemu je tacno problem. Evo kod

public static void main(String[] args) {
System.out.print(rec(5));



}
private static int rec(int n){
if(n==0 || n==1){
return 1;
}
else{
int temp= rec(n-1)+ rec(n-2)+1;
System.out.println("L ("+ n +" ) ="+ temp);
return temp;
}

}
}

A evo sta izbacuje:
L (2) =3
L (3) =5
L (2) =3
L (4) =9
L (2) =3
L (3) =5
L (5) =15
15
 
Odgovor na temu

Milan Milosevic

Član broj: 67
Poruke: 932
*.dynamic.isp.telekom.rs.



+31 Profil

icon Re: Pomoc oko jednog algoritma koji koristi rekurziju15.11.2015. u 19:55 - pre 101 meseci
Da bi svatio kako neka procedura radi koristi breakpoint sistem i prolazak korak po korak kroz proceduru.
Tu možeš da pratiš vrednosti svih promenjivih. Tako najlakše možeš da skapiraš šta ti u funkciji radi i da ispraviš greške u kodu ukoliko ih imaš.
 
Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
188.124.211.*



+62 Profil

icon Re: Pomoc oko jednog algoritma koji koristi rekurziju16.11.2015. u 07:58 - pre 101 meseci
Hehe, rekurzija je cudo .

Probaj sledeci kod:

Code:

private static int recursion(int n){
  if(n==0 || n==1){
  System.out.println("L(" + n + ") = " + 1; 
  return 1;
  }
  else {
    int temp = recursion(n-1) + recursion(n-2) +1;
    System.out.println("L(" + n + ") = " + temp; 
    return temp;
  }
}


Problem je kod tebe sto imas neuobicajen tok rekurzije; obicno rekurzija podrazumeva jedan 'self' poziv, ali ti imas DVA: 'recursion(n-1) + recursion(n-2)' u istoj liniji/komandi. Zato ti indeksi L idu u trojkama: 2-0-1, 3-1-2, 4-2-3 itd.
Ako sam u pravu, trebalo bi da dobijes sledeci izlaz (nisam probao):

L (0) =1
L (1) =1
L (0) =1
L (2) =3
L (0) =1
L (1) =1
L (3) =5
L (1) =1
L (2) =3
L (4) =9
L (2) =3
L (3) =5
L (5) =15
// ovo bi bilo za 6:
//L (3) =5
//L (4) =9
...

Tesko je objasniti, moras staviti breakpoint na svaki println(), pa polako vozi krug po krug i prati vrednosti varijabli. Posebno obrati paznju GDE se tok programa vraca nakon return(). Nije lose da procitas malo i o tome sta je stack; kad to usvojis, sve ce biti kudikamo jasnije.
Srecno!

Pozz
 
Odgovor na temu

Bond123

Član broj: 330809
Poruke: 22
78.104.151.*



Profil

icon Re: Pomoc oko jednog algoritma koji koristi rekurziju16.11.2015. u 23:08 - pre 101 meseci
Hvala Rajko. Zivio!
 
Odgovor na temu

[es] :: Java :: Pomoc oko jednog algoritma koji koristi rekurziju

[ Pregleda: 2461 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.