objasnjenje koda, return funkcije???

[ osmania @ 18.11.2007. 16:14 ] @

hrj ljudi uspio sam code da napisem ali to je bilo skoro otprilike i proradilo kontam skoro sve sta sam uradio ali
ne kontam teoretski nesto?

kada dodje funkcija do n == 0 i vrati return 1, sta se dalje desava .... koliko ce se puta funkcija izvrsiti return, i kako on zna da je fkt(n) toliko koliko bi trebalo da bude???
ne kontam kako ce mi on dati tu vrijednost fkt(n) kad nigdje ne sabira mislim u biti nisam ja dobro skonto tako reci te rekruzivne funkcije... hvala na vasem strpljenju..

evo code:

Code:
int binom(int n, int k)
{
  return fkt(n) /(fkt(k) * fkt(n - k));
}

int fkt(int n)
{
  if(n == 0)
    return 1;
  else
    return n * fkt(n - 1);}

[ perun_ @ 18.11.2007. 16:41 ] @

Neka je n=3. U prvom pozivu fkt(3), vraca 3*fkt(2), sto znaci da odmah ponovo poziva -ju fkt, koja ce sada vratiti 2*fkt(1), ponovo znaci poziva fkt(1) koja vraca 1*fkt(0), koja vraca 1. Dakle sve ukupno rezultat pozivanja f-je fkt(3) ce biti 3*2*1*1=6. Sada vidis da bi isto radilo sa if(n==1), nema potrebe da ides do n==0. Nadam se da je jasnije, kako radi rekurzija?

[ osmania @ 18.11.2007. 17:06 ] @

hej hvala drug uspio sam skontat to ali sada mi je dosao problem koji ne znam kako racuna,,,
evo code:

n=5 izbaci mi 17 kako sada buni me sada vise funkcija koje poziva...
hvala puno:)

Code:
int fkt(int n)
{
  if(n <= 2)
    return 1;

  return 2 * fkt(n - 1) + fkt(n - 2) * fkt(n - 3);
}

[ perun_ @ 18.11.2007. 17:27 ] @

Izgleda da me ipak nisi shvatio. Hajdemo ponovo, posle ovoga ces valjda biti nacisto.

Code:
fkt(5)=2*fkt(4)+fkt(3)*fkt(2)

Sada nam preostaje da nadjemo ponaosob fkt(4), fkt(3) i fkt(2) i ubacimo u ovaj izraz.

Dakle prvo cemo fkt(4), jer je najtezi, a i usput cemo naci i fkt(3) i fkt(2).

Code:

fkt(4)=2*fkt(3)+fkt(2)*fkt(1)

Sada nadjemo fkt(3). Dalje je:

Code:

fkt(3)=2*fkt(2)+fkt(1)*fkt(0)

iz uslova:

Code:

if (n<=2)
return 1;

imamo da je :

Code:

fkt(2)=1
fkt(1)=1
fkt(0)=1

Tako da je:

Code:

fkt(3)=2*1+1*1=2+1=3

Vracamo ovo u izraz za fkt(4) i dobijamo:

Code:

fkt(4)=2*3+1*1=6+1=7

Sada se vracamo u prvi izraz da dobijemo konacno resenje:

Code:

fkt(5)=2*7+3*1=14+3=17

I to je to. Sto kaze Cola: "Imamo cijelu stvar!!!"
Jesmo li sada sve demistifikovali?

Citat:

hvala puno

Nema na cemu!

[ osmania @ 18.11.2007. 17:32 ] @

sad je sve kako treba dok ne nadjem drugi problme sada mi je puno toga jasno... hvala jos jednom...
znaci sve pjeske izracunati i to je to,,,

[ perun_ @ 18.11.2007. 17:38 ] @

Peske izracunavas za proveru rezultata. Ovako ti i nemas potrebu da racunas osim za testiranje programa. I kada pises program za najobicnije mnozenje, sabiranje brojeva, ti ces prilikom izvrsavanja izracunati sam, cisto da se uveris da je to to. A rekurzija se kao resenje nekih problema jednostavno namece sama po sebi, najklasicniji primer je faktorijel. Ili recimo Hanojske kule...

[ osmania @ 18.11.2007. 17:54 ] @

evo ga jos jedan problem
m =3 i n=3
multi mi je jasan bez ikakvih problema ali power kad poziva multi sta gde kome sta pripada?
m = m a multi (m,n-1) = power (m, n-1) ili???
buni me sada kad se multi pozove iz power sta ceonda biti sta se kome dodjeljuje koje vrijednosti....
hvala drug

Code:
int mult(int m, int n)
{
  if(n == 0 || m == 0)
    return 0;
  if(n<0) {
   n=-n;
   m=-m;
  }

   return m + mult(m, n - 1);

}

int power(int m, unsigned int n)
{
  if(m == 0)
    return 0;
  if(n == 0)
    return 1;
  return mult(m, power(m, n - 1));
}

[ perun_ @ 18.11.2007. 20:56 ] @

Imamo f-ju power (3,3).
Ona ce da vrati mult (3,power(3,2))
power (3,2) ce da vrati mult(3,power(3,1))
tako da predhodna f-ja ustvari vraca mult(3,mult(3,power(3,1)))
power (3,1) vraca mult(3,power(3,0))
Tako da prva ustvari vraca mult(3,mult(3,mult(3,power(3,0))))
power(3,0) vraca 1
Sada prvobitna vraca konacno mult(3,mult(3,mult(3,1)))
Sada nam ostaje da "rascistimo" sta vracaju ovi silni multovi (*eb'o ih ko ih smisli, pocecemo da mucamo od ovoga

)
idemo "iznutra", sta vraca mult(3,1)
vraca 3+mult(3,0), a mult(3,0) vraca 0, sto znaci 3, samim tim ona nasa glavna vraca
mult(3,mult(3,3))
Sta vraca mult (3,3)
Prvi korak 3+mult(3,2) drugi: 3+3+mult(3,1) treci: 3+3+3+mult(3,0) cetvrti:3+3+3+0=9
Sto znaci da nasa prvobitna vraca mult(3,9)
A i to cemo sada izracunati :
mult(3,9)=3+mult(3,8 )=3+3+mult(3,7)=3+3+3+mult(3,6)=3+3+3+3+mult(3,5)=3+3+3+3+3+mult(3,4)=3+3+3+3+3+3+mult(3,3)=3+3+3+3+3+3+9
Poslednja devetka je mult(3,3) sto smo izracunali u proslom koraku
Sveukupno, ovo sve vraca 6*3+9=27

Dokaz:
(file /root/Desktop/proba/proba.cpp)

Code:

#include <iostream.h>
int mult(int m, int n)
{
  if(n == 0 || m == 0)
    return 0;
  if(n<0) {
   n=-n;
   m=-m;
  }

   return m + mult(m, n - 1);

}

int power(int m, int n)
{
  if(m == 0)
    return 0;
  if(n == 0)
    return 1;
  return mult(m, power(m, n - 1));
}
int main()
{
    cout<<power(3,3);
    return 0;
}

Rezultat pokretanja:

Code:

root@slack:~/Desktop/proba# g++ proba.cpp
root@slack:~/Desktop/proba# ./a.out
27
root@slack:~/Desktop/proba#

Jasno kao dan!

[ caplja caplja @ 18.11.2007. 23:17 ] @

Citat:

A rekurzija se kao resenje nekih problema jednostavno namece sama po sebi, najklasicniji primer je faktorijel. Ili recimo Hanojske kule..

Nas su ucili na fakultetu da se rekurzija koristi za probleme kod kojih se unapred ne zna koliko ce biti potrebno koraka obaviti za resenje istih (npr. operacije nad binarnim stablima) a da su faktorijeli bas primer za problem kod kojeg ne treba primeniti rekurziju.

[ perun_ @ 18.11.2007. 23:30 ] @

Slazem se sa tobom. Rekurziju po mom misljenju treba uvek izbegavati. Ovo sam rekao, bukvalno iz knjiga, gde god vidis bilo sta o rekurziji pomene se faktorijel i Hanojske kule...:)
Narocito je suludo upotrebljavati rekurziju u funkciji za stepenovanje, kao ova predhodna. Mislim toliki pozivi drugih f-ja prosledjivanje parametara, cisto bacanje resursa a i na kraju krajeva znatno je teze i realizovati i pratiti takve stvari. Ovde je for petlja zakon (za n-3, tri prolaza i toliko). I u binarnim stablima je svakako u ogromnoj vecini slucajeva moguce odraditi stvari pomocu do-while, ili while petlji, tako da bih ih licno i tu maksimalno izbegavao...

[ osmania @ 19.11.2007. 09:31 ] @

ljudi sve je to super naucio sam nesto ali sada pitanje glasi zasto mi se ovaj code zakuca.
sve prodje bez ikakvih gresaka i pokrene se program ukucam 7 i 9 i izracuna mi multi na power samo izbaci mi program zatvoriti kao ono crknut ili trazi rjesenje preko interneta (pod vistom )
to mi radi ka ukucam 7 i 9 ako ukuca 9 u 7 radi kako treba...
hvala puno :)
radim pod dev c++ zadnji

Code:
#include <iostream>
#include <math.h>
using namespace std;

int mult(int m, int n)
{
  if(n == 0 || m == 0)
    return 0;
  if(n<0) {
   n=-n;
   m=-m;
  }
  return m + mult(m, n - 1);    //m*n= m+m*(n-1)

}

int power(int m, unsigned int n)
{
  if(m == 0)
    return 0;
  if(n == 0)
    return 1;
  return mult(m, power(m, n - 1));
}

int main()
{
  int z;
  int m, n;
  do {
    cout << "m,n: ";
    cin >> m >> n;
    cout << "Mult: " << mult(m, n) << endl;
    if(n >= 0)
      cout << "Power: " << power(m, n) << endl;

    cout << endl;
    cout << "jos jednom? (0=prekini) ";
    cin >> z;
  } while(z != 0);
  return 0;
}

[ perun_ @ 19.11.2007. 12:29 ] @

Imajuci u vidu da je 7 na 9 = 40 353 607 ocigledno je da opseg integer-a nije prebacen. Jedino sto mi pada na pamet je prekoracenje memorije na steku prilikom silnih poziva f-ja power i mult. Mada kako tacno to ide po brojkama i zauzetosti pojma nemam..

Sve u svemu jos jedan dokaz da rekurziju treba izbegavati.

[ osmania @ 19.11.2007. 12:53 ] @

e vidim da si zagrijan as rekurziom, de mi objasni ovaj code onaj sve sam konto ali ovaj pogubim se jer ne znam vise gdje sta koga poziva???

Code:
int f(int n)
{
  if(n == 0)
    return 0;
  return h(n) + g(n - 1);
}

int g(int n)
{
  if(n == 0)
    return 0;
  return 2 * f(n);
}

int h(int n)
{
  if(n == 0)
    return 1;
  return n * h(n - 1);
}

[ perun_ @ 19.11.2007. 13:00 ] @

Koju f-ju pozivas iz main-a? f() ili g()? Da ne pokusavam da objasnjavam i ono sto ne treba, a i da skratimo vreme objasnjavanja...
P.S. Zagrejan sam protiv rekurzije!

[ osmania @ 19.11.2007. 13:02 ] @

izvini stari do mene je zaboravi mail da stavim ovo je u main kod mene:

cout << "f(n): " << f(n) << endl;
cout << "g(n): " << g(n) << endl;
cout << "h(n): " << h(n) << endl;

[ perun_ @ 19.11.2007. 13:42 ] @

Uzecemo n=3.
Prvo f(3)
vraca h(3)+g(2)
sada cemo h(3)
vraca 3*h(2)
a prvobitna: 3*h(2)+g(2)
sada h(2)
vraca 2*h(1)
prvobitna 3*2*h(1)+g(2)
h(1) vraca
1*h(0)
a nasa stara: 3*2*1*h(0)+g(2)
h(0)=1
glavna: 3*2*1*1+g(2)
sada prelazimo na g(2)
vraca 2*f(2)
a glavna 6+2*f(2)
sada f(2)=h(2)+g(1)
sto ce reci: f(3)=6+2*(h(2)+g(1))
h(2)= 2*h(1)=2*(1*h(0))=2(1*1)=2
g(1)=2*f(1)=2*h(1)+g(0)=2*1*h(0)+0=2
dakle f(3)=6+2*(2+2)=14

h(3)=3*h(2)=3*2*h(1)=3*2*1*h(0)=3*2*1*1=6

g(3)=2*f(3)=2*14=28

[ osmania @ 19.11.2007. 15:44 ] @

hej drug hvala ti puno ovo je bilo super necu te vise zamarati (mozda ako bas hitno bude) ode da jos gledam ovo sve pa da vidimo dokle cu da svarim ovo sve ;)
pozz

[ perun_ @ 19.11.2007. 16:14 ] @

Nema na cemu. Samo napred!

[ Sephiroth? @ 23.12.2007. 23:36 ] @

Samo jedan dodatak u vezi rekurzije. Rekurzija SKORO NIKAD (u 99% slucajeva) nije najbrzi i najefikasniji izbor algoritma. Iako danasnji sistemi mnoogo bolje rukuju sa sistemskim pozivima, opet je poprilicno spora. Ipak, ona se koristi, ali ne radi brzine nego da problem konceptualno jednostavnije rijesi. Svaki rekurzivni kod se moze zamjeniti sa ili:

- while petljom (linearno rjesavanje)
- implementacijom pomocu stacka

Cisti primjer su fibonaccievi brojevi, znaci koji se broj nalazi na nekom mjestu niza: 1,1,2,3,5,8,12,21 ...

Code:

// rekurzivno
int fr(int n)
{
  if (n == 0 || n == 1)
  return 1;
  return fr(n-1)+fr(n-2);
}

Code:

//linearno (while petlja, niz...)
int fl(int n)
{
  int a[n+1];
  for (int i=0; i<=n; ++i)
  {
   if (i == 0)
   {
    a[0] = 1;
   } else if (i == 1)
   {
    a[1] = 1;
   } else
       {
        a[i] = a[i-1] + a[i-2];
       }
  }
return a[n];
}

Ako usporedimo rezultate:

Code:

int main(void)
{
      int n, izbor, c, rezultat;
      cout << "Unesite broj n: ";
      cin >> n;
      cout << "\nDa li zelite rekurzivnu ili linearnu obradu?" << endl;
      cout << "  - 1 - rekurzivno" << endl;
      cout << "  - 2 - linearno" << endl;
      cout << "izbor : ";
      cin  >> izbor;

      switch (izbor)
      {
       case (1):
        c = clock();
        rezultat = fr(n);
        c = clock() - c;
        break;
       case (2):
        c = clock();
        rezultat = fl(n);
        c = clock() - c;
        break;
       default:
        cout << "\nPogresan unos!\n\n";
        system("pause");
        return EXIT_SUCCESS;
      }

      cout << "\nRezultat je : " << rezultat << ", vrijeme obrade : " << c << "\n\n";
      system("pause");
      return EXIT_SUCCESS;
}