PDA

Visualizza la versione completa : [C++] Programma ricorsivo


RooccoXXI
18-12-2011, 14:09
Ciao a tutti.
Sto cercando di rifare un po' di vecchi esami per preparare il mio e mi sono imbattuto in un programmino che non riesco proprio a capire.

Dovrei dire cosa visualizza a schermo e dare un nome alle due funzioni (in particolare capire cosa fanno matematicamente)...

Il programma è il seguente:


#include <iostream>
using namespace std;

int f(int x, int y)
{
if(y <= 0) return x;
return f(x+1, y-1);
}

int g(int x, int y)
{
if(y <= 1) return x;
return f(x, g(x, y-1));
}

int main ()
{
cout << g(6, 3) << endl;

return 0;
}

Qualcuno può aiutarmi please?
GRazie.

linoma
18-12-2011, 14:40
Forse ritorna gli 0 di una funzione :)

RooccoXXI
18-12-2011, 14:53
Originariamente inviato da linoma
Forse ritorna gli 0 di una funzione :)

Si?
Potresti spiegarmi passo per passo a come si arriva a tale conclusione please?

Ho qualche problema a capire cosa fanno le funzioni ricorsive (malgrado abbia capito il concetto...).

Infatti nell'esame dell'anno dopo ne ho trovata una simile e mi sono bloccato nuovamente.



int f(int a, int b)
{
if (a < 1) return b;
else return f(a-1, a*b);
}

Anche in questo caso devo spiagare cosa fa e dare una versione non ricorsiva. Domanda: se nel test non capisco cosa fa una funzione ricorsiva, c'è comunque un modo (un "algoritmo") per arrivare a trovare quella iterativa equivalente?

oregon
18-12-2011, 14:56
Restituisce il prodotto dei due valori passati

linoma
18-12-2011, 15:00
Pare che chiedere spiegazioni sia fuori regolamento. In verita ho buttato ad indovinare :)

RooccoXXI
18-12-2011, 15:08
Originariamente inviato da linoma
Pare che chiedere spiegazioni sia fuori regolamento. In verita ho buttato ad indovinare :)

Fuori regolamento? -.-

Comunque a me non interessa tanto cosa fa questo programma in particolare, ma capire come abbordare in generale questo tipo di problema...

RooccoXXI
18-12-2011, 15:09
Originariamente inviato da oregon
Restituisce il prodotto dei due valori passati

In pratica richiama inutilmente sé stessa a volte, calcolando ogni volta il prodotto e poi restituendo questo risultato alla funzione precedente, che lo restituisce a sua volta fino ad arrivare alla prima funzione chiamante?

Se è così ora lo vedo, ma nel primo esempio ancora non capisco...

ramy89
18-12-2011, 15:39
Partiamo da questa:


#include <iostream>
using namespace std;

int f(int x, int y)
{
if(y <= 0) return x;
return f(x+1, y-1);
}


Restituisce la somma tra x e y, ma solo se y>0.
Altrimenti restituisce x.
Il perchè sta nel codice, tradotto significa:
"Se y non è positivo ritorna x, altrimenti incrementa x y volte e ritorna x"

Questa:



int g(int x, int y)
{
if(y <= 1) return x;
return f(x, g(x, y-1));
}



Questa è la funzione moltiplicazione, ma funziona solo se y>1.
Se y>1 ritorna la somma di x più la moltiplicazione di x per y-1.
Il che equivale a dire che ritorna la moltiplicazione tra x e y, perchè quando y sarà 1, a x gli avrai sommato x y-1 volte.
Ti faccio un esempio:
Ho g(4,3) -> f(4, f(4,g(4,2)) -> f(4, f(4,f(4,g(4,1))))
g(4,1) = 4, allora g(4,3) = f(4, f(4,4)) = f(4,8) = 12.



int main ()
{
cout << g(6, 3) << endl;

return 0;
}

Nel main stampa la moltiplicazione tra 6 e 3, se non erro dovrebbe stampare 18, prova a compilarlo e fammi sapere il risultato.

RooccoXXI
18-12-2011, 15:44
Originariamente inviato da ramy89
Partiamo da questa:


#include <iostream>
using namespace std;

int f(int x, int y)
{
if(y <= 0) return x;
return f(x+1, y-1);
}


Restituisce la somma tra x e y, ma solo se y>0.
Altrimenti restituisce x.
Il perchè sta nel codice, tradotto significa:
"Se y non è positivo ritorna x, altrimenti incrementa x y volte e ritorna x"

Questa:



int g(int x, int y)
{
if(y <= 1) return x;
return f(x, g(x, y-1));
}



Questa è la funzione moltiplicazione, ma funziona solo se y>1.
Se y>1 ritorna la somma di x più la moltiplicazione di x per y-1.
Il che equivale a dire che ritorna la moltiplicazione tra x e y, perchè quando y sarà 1, a x gli avrai sommato x y-1 volte.
Ti faccio un esempio:
Ho g(4,3) -> f(4, f(4,g(4,2)) -> f(4, f(4,f(4,g(4,1))))
g(4,1) = 4, allora g(4,3) = f(4, f(4,4)) = f(4,8) = 12.



int main ()
{
cout << g(6, 3) << endl;

return 0;
}

Nel main stampa la moltiplicazione tra 6 e 3, se non erro dovrebbe stampare 18, prova a compilarlo e fammi sapere il risultato.

Si, si. Avevo già provato a compilarlo e stampa proprio 18. Quindi ho immaginato che fosse 6 * 3, ma non ero riuscito a vedere che stampava 18 sulla carta. Però il metodo che hai usato (scrivere proprio tutte le funzioni) non è male! È un vero macello se i numeri sono grandi, ma così sembraun'ottimo moto, così si risolve sal più interno al più esterno con "facilità".
È il metodo con cui procedere? (E se da numeri grandi io la scomposizione la faccio comunque su numeri piccoli!)

RooccoXXI
18-12-2011, 15:58
Altro programma...
(Ormai ho capito che la recursione gli piace assai e che sicuramente ci sarà all'esame... -.-)


#include <iostream>
using namespace std;

bool f(int nombre);

bool g(int nombre)
{
if(nombre == 0) return true;
else return f(nombre-1);
}

bool f(int nombre)
{
if(nombre == 1) return true;
else return g(nombre-1);
}

int main ()
{
int nombre(4);

cout << "Nombre entier: " << endl;
cin >> nombre;

if(g(nombre)) cout << nombre << " est ...(A)..." << endl;
if(f(nombre)) cout << nombre << " est ...(B)..." << endl;

return 0;
}

Mi è venuta l'illuminazione e direi che dice se un numero è pari o dispari, quindi (A)=pari, (B)=dispari.

Però mi è proprio venuta così, a pelo. Non so se é giusta e nel caso lo fosse, comunque, il mio problema persiste...!

Loading