Recursivitate

[•Peter]

Salut. Am si eu o nelamurire la recursivitate.
Cand rezolv pe caiet urmatoarea secventa de cod:

Cod:

void f(int x,int y)
{
    if(x<=y)
    {
        f(x+1,y);
        cout<<x;
    }
}

ajung la rezultatul 123.
Insa cand o compilez pe calculator imi afiseaza 321.
Eu am gandit-o asa:
   1<=3 -> {f(2,3), scrie 1}
   2<=3 -> {f(3,3), scrie 2 }
   3<=3 -> {f(4,3), scrie 3 }
   4<=3 (fals) -> STOP
   
   Si ar trebui sa afiseze 1,2,3 in ordinea in care le-am aflat.
   Am gandit-o gresit? Spuneti-mi va rog cum ar trebui sa o gandesc corect. Multumesc.

[•CosminRusu]

Uite aici si aici !
Spor.

[•Peter]

Multumesc mult

Din secventa asta insa:

Cod:

int MyFunc(int counter) {
    if(counter == 0) {
        return counter;
    }
    else {
       MyFunc(counter - 1);
       cout<< counter;
}}

tot nu imi dau seama de ce afiseaza 1,2,3,..., counter.
 Raman tot la ideea ca daca ii dau lui counter valoarea 7, de exemplu, ar trebui sa imi afiseze 7654321. O gandesc la fel ca pe anterioara. Explica-mi te rog daca vrei pt counter=3... sau 4, o valoare mai mica.  Multumesc mult

[•CosminRusu]

Poi daca ai te-ai fi uitat pe ce ti-am dat si ai fi inteles ti-ai fi dat seama de ce afiseaza aia.
O sa trec peste teoria cu stiva si asa.
Trebuie sa intelegi o chestie foarte simpla: Cand apelezi o functie programul tau se duce direct la inceputul functiei si abia ce se termina functia asta apelata apoi continua de unde a ramas.

Adica tu apelezi asa:

1. F(4)

iti intra in else din motive (clare, sper), acum apeleaza F(3):   
                                                                           iti intra iarasi in else (din aceleasi motive:)) ), apeleaza F(2)...
Interesant este ce se intampla la F(0), intra inf if - ul acela si returneaza valoarea 0.
Din cauza faptului ca programul tau a fost apelat de mai multe ori el revine sa "termine" ce are de facut. Adica revine la F[1] ca sa faca instructionile de dupa apelare, adica cout << counter. In cazul nostru afiseaza 1.
Se observa ca acum se termina functia.
Programul revine la F(2), F(3), F(4), de fiecare data afisand counter-ul.
Deci ordinea in care sunt afelate functiile este F(4), F(3)...F(0), iar afisarea e chiar invers.
Iti sugerez sa studiezi mai bine (din manual sau de pe net) revursivitatea. Este un concept esential pentru un programator.

http://www.infoarena.ro/blog/putina-recursivitate

Uite poate intelegi din comentariile de la articolul asta.

Succes!

[•Peter]

Multumesc mult. Deci ordinea se face invers de cum ar veni in mod normal )  
Insa am incercat mai multe tipuri de programe si am "descoperit" ca daca "cout" e prima instructiune si apoi dupa aia se apeleaza functia, ordinea afisarii va fi alta:

Pentru secventa:

Cod:

#include <iostream>
using namespace std;
int MyFunc(int counter) {
    if(counter == 0) {
        return counter;
    }
    else
	{
 	cout<< counter;
MyFunc(counter - 1);
	}
}
int main()
{
	int counter;
	cin>>counter;
	MyFunc(counter);
}

Pentru valoarea 7 de exemplu se va afisa 7654321.

Iar pentru secventa :

Cod:

#include <iostream>
using namespace std;
int MyFunc(int counter) {
    if(counter == 0) {
        return counter;
    }
    else
	{
MyFunc(counter - 1);
	cout<<counter;
	}
}
int main()
{
	int counter;
	cin>>counter;
	MyFunc(counter);
}

se va afisa 1234567 ( pentru counter=7).
Imi poti explica putin de ce? Multumesc.
 

[•CosminRusu]

Poi fiindca prima data afisezi si apoi apelezi functia...  .

[•Peter]

Am inteles acum, mai ales ca am mai facut si cateva exemple din modele de bac. Iti multumesc mult