[C++] Programma ricorsivo

[RooccoXXI]

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]

Forse ritorna gli 0 di una funzione

[RooccoXXI]

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]

Restituisce il prodotto dei due valori passati

[linoma]

Pare che chiedere spiegazioni sia fuori regolamento. In verita ho buttato ad indovinare

[RooccoXXI]

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]

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]

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]

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]

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...!