Imprimă pagina - Recursivitate

Titlul: Recursivitate
Scris de: Catalin din Ianuarie 13, 2014, 15:29:00

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.

Titlul: RÄƒspuns: Recursivitate
Scris de: Cosmin Rusu din Ianuarie 13, 2014, 15:36:13

Uite aici (https://www.youtube.com/watch?v=ozmE8G6YKww) si aici (http://stackoverflow.com/questions/5631447/how-recursion-works-in-c) !
:) Spor.

Titlul: RÄƒspuns: Recursivitate
Scris de: Catalin din Ianuarie 13, 2014, 15:52:03

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 :D

Titlul: RÄƒspuns: Recursivitate
Scris de: Cosmin Rusu din Ianuarie 13, 2014, 16:28:54

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!

Titlul: RÄƒspuns: Recursivitate
Scris de: Catalin din Ianuarie 13, 2014, 16:49:40

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.

Titlul: RÄƒspuns: Recursivitate
Scris de: Cosmin Rusu din Ianuarie 13, 2014, 19:00:49

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

Titlul: RÄƒspuns: Recursivitate
Scris de: Catalin din Ianuarie 13, 2014, 19:04:45

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Catalin din Ianuarie 13, 2014, 15:29:00