Programiranje 107: Rekurzija

Za razumevanje rekurzije biće vam potrebno znanje funkcija.
Rekurzivne funkcije su one koje same sebe pozivaju. Recimo za faktoriel nekog broja: f(1)=1, f(x)=x*f(x-1).
Pokazaću vam rekurziju preko jednog semi-jednostavnog primera. Unećemo dva broja: n i k. Cilj će biti da ispišemo sve brojeve sa k cifara u bazi n. Broj u bazi n je broj koji se sastoji samo od cifara manjih od n. Na primer, broj 7 u svim bazama od 2 do 10: 111, 21, 13, 12, 11, 10, 7, 7, 7. Najčešće se koriste baze 2 (binarni), 8(oktalni) i 10(dekadni). Da bi naš broj mogao biti veoma dug mi ćemo ga čuvati u nizu. Pošto počinjemo od broja 0, to znači da će svi članovi niza biti 0. Sad hajde da vidimo kako se broji u bazi recimo 5. 001, 002, 003, 004, 010, 011, 012, 013, 014, 020, 021... Dakle prvo stavljamo da je poslednja cifra od 0 do 4. Kada stigne do četiri opet se vraća na nulu, a druga od pozadi cifra se povećava, što znači da se poslednja cifra najbrže menja. U for petljama se najbrže menja ona koja je najdublja, ona koja je poslednja u nizu, to znači da prvo treba da pišemo menjanje za prvu cifru a onda sve dublje i dublje. Pogledajte kod i da ga polako objasnim:

void rek(int d)
{
if(d<k)
{
for(int i=0; i<n; i++)
{
a[d]=i;
rek(d+1);
}
}
else
{
for(int i=0; i<n; i++)
{
cout<<a[i];
}
cout<<endl;
}
}
void main()
{
cin>>n>>k;
rek(0);
}

Prvo funkcija je void. Ona ne vraća nijednu vrednost, zato što ispisuje sve slučajeve. Jedini argument je integer d koji prestavlja na kojoj se cifri trenutno nalazimo (crvena linija na snimku). Prvo proveravamo dali je trenutna cifra prešla poslednju, ako nije stiglo do kraja broja. Ako nije stavljamo trenutnu cifru na svaku moguću pokretajući funkciju za svaki od tih slučajeva. Ako je stiglo do kraja onda samo ispisuje niz.
Hajde da vam objasnim na primeru, n=3, k=3. Niz:

NAN

NAN

NAN

Prvo pokrećemo funkciju za nulti član. Pošto je d==0 a to je manje od k onda prelazimo u prvi deo. U prvom prolasku i=0 i a[0]=0.

0

NAN

NAN

Sada pokrećemo funkciju rek opet za član d+1==1. d je opet manje od k pa prelazimo u prvi deo. i=0 pa je a[1]=0.

0

0

NAN

Opet pokrećemo funkciju rek sada za d+1=2. Prelazimo na prvi deo i stavljamo da je i=0, pa je a[2]=0.

0

0

0

Prelazimo na ispis. Pošto je funkcija pokrenuta za d+1=3 što nije manje od k ispisujemo ceo niz pa je u našoj konzoli:

000

Kada se to završilo "vraćamo se za jedan korak" odnosno vraćamo se na ono mesto kada smo pozvali funkciju. Tada smo namestili a[2]=0, zato povećavamo i za jedan pa je i=1, onda namestamo a[2]=1:

0

0

1

Onda pokrećemo funkciju za 3, odnosno ispis i naša konzola sada ispisuje:

001

Opet se povećava i za jedan pa je a[2]=2:

0

0

2

Poziva se funkcija rek za 3 što daje novi ispis:

002.

Kada je i stiglo do 3 vraćamo se jedan korak unazad, odnosno kada smo namestili a[1]=0,tada je i bilo 0. Povećavamo i pa je sad 1. Stavljamo da je a[1]=1 i niz nam izgleda ovako:

0

1

2

Pokreće se funkcija rek za 2 i pravi se novo i=0. pa je sada a[2]=0:

0

1

0

Ispisuje:

010

To se radi dok prvo i ne stigne do 3, tada se uslov prvog prekida.

Ovaj primer ću vam napisati sa for petljama, da bi ste videli kako može još da radi:

int n,a[1000];

cin>>n;

for(int i1=0; i1<n; i1++)

{

a[0]=i1;

for(int i2=0; i2<n; i2++)

{

a[1]=i2;

for(int i3=0; i3<n; i3++)

{

a[2]=i3;

cout<<a[0]<<a[1]<<a[2]<<endl;

}

}

}

Kao što vidite kada bi smo hteli da dodamo još jednu cifru morali bi da dodamo još koda, a cilj je da možemo da biramo broj cifara i da taj broj bude veliki do recimo 10000 i bilo bi vrlo "neekonomicno" da kopiramo jedan deo koda 10000 puta. Ako niste shvatili rekurziju to je u redu, meni je trebalo dosta vremena, način na koj sam naučio jeste da sam uzeo zbirku (nije za C++ jezik) i uradio desetak zadataka (većinu pogledao rešenja) i naučio sam (za pokazivače mi je trebalo još duže), zato ću vam dati šest zadataka kao i uvek pa se izvežbajte, ako vam nije dovoljno izmislite neki slobodno, napravite neki program koji će vam pomoći u svakodnevnom životu.

1. Napišite rekurzivnu funkciju koja izračunava n! (n*(n-1)*(n-2)*...*3*2*1).
2. Napišite rekurzivnu funkciju koja izračunava trougao brojeve (n+(n-1)+(n-2)+...+3+2+1).
3. Napišite rekurzivnu funkciju koja nalazi minimum niza.
4. Napišite rekurzivnu funkciju koja izračunava NZD i NZS za ceo niz.
5. Napišite rekurzivnu funkciju koja u matrici nalazi najveći oblik sačinjen od susednih polja matrice čije su vrednosti iste.
6. Ćovek želi da pređe iz jedne tačke do druge tačke na matrici. Napišite rekurzivnu funkciju koja određuje najkraći put tako da čovek ne sme da zgazi na polje matrice koja ima parnu vrednost (sme da se kreće samo levo, desno, gore i dole).

Rešenja prethodnog domaćeg:

/*1*/

#include <iostream>

using namespace std;

bool paran(int n)

{

if(n%2==0)return true;

else return false;

}

void main()

{

int n;

cin>>n;

cout<<paran(n);

}

/*2*/

#include <iostream>

using namespace std;

int n;

int min(int a[])

{

int m;

m=999999;

for(int i=0; i<n; i++)if(a[i]<m)m=a[i];

return m;

}

void main()

{

int a[100];

cin>>n;

for(int i=0; i<n; i++)cin>>a[i];

cout<<min(a);

}

/*3*/

#include <iostream>

using namespace std;

int n;

int NZD(int a, int b)

{

int t=a;

while(!((a%t==0)&&(b%t==0)))t--;

return t;

}

int NZS(int a, int b)

{

int t=a;

while(!((t%a==0)&&(t%b==0)))t++;

return t;

}

void main()

{

int a,b;

cin>>a>>b;

cout<<NZD(a,b)<<' '<<NZS(a,b)<<endl;

}

/*4*/

#include <iostream>

using namespace std;

int vrednost(int a[100] [100],int ip,int jp,int np,int mp)//izvinjavam se sto nisam napomenuo da za visedimenzionalne nizove(matrice) treba da se zadaje velicina.

{

int s(0);

for(int i=ip; i<ip+np; i++)

for(int j=jp; j<jp+mp; j++)

s+=a[i][j];

return s;

}

void main()

{

int a[100][100],n,m,ip,jp,np,mp;

cin>>n>>m;

for(int i=0; i<n; i++)

for(int j=0; j<m; j++)

cin>>a[i][j];

cin>>ip>>jp>>np>>mp;

cout<<vrednost(a,ip-1,jp-1,np,mp)<<endl;

}

/*5*/

#include <iostream>

using namespace std;

bool palindrom(int n)

{

int a[9];

int m=n;

int k=-1;

while(m>0)

{

k++;

a[k]=m%10;

m/=10;

}

k++;

bool jeste=true;

for(int i=0; i<k/2; i++)

{

if(a[i]!=a[k-i-1])

{

jeste=false;

break;

}

}

return jeste;

}

void main()

{

int n;

cin>>n;

cout<<palindrom(n)<<endl;

}

/*6*/

#include <iostream>

using namespace std;

int reverse(int n)

{

int m(0);

while(n>0)

{

m*=10;

m+=n%10;

n/=10;

}

return m;

}

void main()

{

int n;

cin>>n;

cout<<reverse(n)<<endl;

}