[C++] Programma ricorsivo

[ramy89]

È il metodo con cui procedere? (E se da numeri grandi io la scomposizione la faccio comunque su numeri piccoli!)

Potresti dimostrare che funziona per un generico numero n.
Riguardo alla f(x,y) puoi dire che:
-Se y<=0 ritorna x ;
-Se y>0 ritorna f(x+1,y-1).

Devi riuscire a calcolare qual'è la clausola di chiusura della funzione ricorsiva:
f(x,y) = f(x+1,y-1) passo 1 con y>>0
f(x+1,y-1)=f(x+2,y-2) passo 2
f(x+2,y-2)=f(x+3,y-3) passo 3
f(x+k,y-k)=f(x+k,y-k) passo k con k=y, quindi è uguale a f(x+y , 0)=x+y


Per quanto riguarda la funzione moltiplicazione, avendo dimostrato che f(x,y) è la funzione somma, puoi dire che la g(x,y):
-Se y<=1 ritorna x;
-Se y>1 ritorna x+g(x,y-1) perchè f(x,y) è la funzione somma e l' hai dimostrato
Se y>>1:
g(x,y)= x+g(x,y-1) passo 1
g(x,y) = x+x+g(x,y-2) passo 2
g(x,y) = 3x + g(x,y-3) passo 3
g(x,y)= k x + g(x, y-k) passo k con k=y-1, quindi è l' equivalente di:

g(x,y)=(y-1) x + g(x,1) g(x,1) sappiamo che è uguale a x, allora:
g(x,y==(y-1) x + x = y x

[ramy89]

#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);
}

Il problema di queste due funzioni (mutualmente) ricorsive è che se gli passi un numero negativo la ricorsione non termina più.
g(-4) -> f(-5) -> g(-6) -> ...
In generale si, la g(nombre) ritorna 1 se il numero è pari, la f(nombre) ritorna 1 se il numero è dispari, ma se passi un numero dispari alla g(nombre) la ricorsione non termina più, così come se passi un numero pari alla f(nombre) non termina.
Se hai lo stack sufficientemente grande e passi ad esempio 2 alla f(nombre), può succedere che invece di andare in segmentation fault vai in underflow, e riparti da 2^32-1, che è dispari per cui ti ritorna true.
Io le modificherei così:

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

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

Così dovrebbe funzionare per tutti i numeri naturali compreso zero, ma non per i numeri negativi.
Prova a compilarlo.

[RooccoXXI]

Originariamente inviato da ramy89

#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);
}

Il problema di queste due funzioni (mutualmente) ricorsive è che se gli passi un numero negativo la ricorsione non termina più.
g(-4) -> f(-5) -> g(-6) -> ...
In generale si, la g(nombre) ritorna 1 se il numero è pari, la f(nombre) ritorna 1 se il numero è dispari, ma se passi un numero dispari alla g(nombre) la ricorsione non termina più, così come se passi un numero pari alla f(nombre) non termina.
Se hai lo stack sufficientemente grande e passi ad esempio 2 alla f(nombre), può succedere che invece di andare in segmentation fault vai in underflow, e riparti da 2^32-1, che è dispari per cui ti ritorna true.
Io le modificherei così:

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

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

Così dovrebbe funzionare per tutti i numeri naturali compreso zero, ma non per i numeri negativi.
Prova a compilarlo.

Infatti l'esercizio consisteva anche a trovare gli eventuali problemi! =).

Grazie mille davvero per i consigli e le delucidazioni. Mi sembra più o meno di aver capito. In settimana provo a rifare altri esami, eventualmente posterò ancora.

Grazie!