ricorsione c++

[crasty7]

salve ragazzi ho un problema con la ricorsione ancora non riesco a capirla bene! vi posto sotto la traccia del programma con il relativo codice ma non riesco a fare la media ricorsivamente! grazie in anticipo per l'aiuto! ps: aggiungo che nel codice trovate una prova di ricorsione ma è buttata giù per prova!

/*Si scriva un programma in linguaggio C che tramite:
la funzione leggi(), legga a terminale i dati di N studenti
(con N definito come la costante 4)
costituiti da Nome, Cognome, Voto, e li inserisca in un vettore;
calcoli con la funzione media() la media dei voti;
stampi a terminale i nominativi di ciascuno studente;
stampi poi a terminale il voto medio.*/


#include<iostream>
#include<String>
using namespace std;
void leggi(struct tipo1 p[4],int n);
int media(struct tipo1 p[4], int n);
struct tipo1{
string nome;
string cognome;
int voto;
};


int main(){
int n=4;
int k;
struct tipo1 *p;
p=new tipo1[n];
leggi(p,n);
k=media(p,n);
cout<<"la media e'"<<k<<endl;

system("pause");
return 0;
}


void leggi(struct tipo1 p[4],int n){
int i=0;
for (i=0; i<n; i++){
cout<<"inserisci nome cognome e voto"<<endl;
cin>>p[i].nome;
cin>>p[i].cognome;
cin>>p[i].voto;
}
}


int media(struct tipo1 p[4], int n){

if (n<0){

return 0;
}
else{

return media(p,n-1);
}

}

[Scara95]

Per implementarla ricorsivamente devi necessariamente dividerla in un wrapper + una funzione con qualche parametro di supporto.

Questa è una delle possibili soluzioni:

double media1(struct tipo1 p[], int n, int i, double acc) {
  if(n == i) {
    return acc/n;
  }
  else {
    return media1(p, n, i+1, acc+p[i]);
  }
}

double media(struct tipo1 p[], int n){
  if (n<=0){
return 0;
  }
  else{
    return media1(p, n, 0, 0.0);
  }
}

[Samuele_70]

Un'altra possibile soluzione

double media( struct tipo1 *p, int n, double &mediaVoti )
{
    if( n )
    {
        cout<<"Nome : "<<p[n].nome<<" \t"<<p[n].cognome<<" \t"<<p[--n].voto<<endl;
        media( p, n, (mediaVoti += p[n].voto) );
    }
    return mediaVoti / ++n;
}

da richiamare in questo modo

    double mediaVoti = 0.;
    mediaVoti = media( p, N, mediaVoti);

[Scara95]

Un'altra possibile soluzione

double media( struct tipo1 *p, int n, double &mediaVoti )
{
    if( n )
    {
        cout<<"Nome : "<<p[n].nome<<" \t"<<p[n].cognome<<" \t"<<p[--n].voto<<endl;
        media( p, n, (mediaVoti += p[n].voto) );
    }
    return mediaVoti / ++n;
}

da richiamare in questo modo

    double mediaVoti = 0.;
    mediaVoti = media( p, N, mediaVoti);

NO, decisamente no.
Pessima.
Se utilizzi una variabile per mantenere lo stato perdi tutto.
Il tuo codice è pieno di stati!!

Inoltre questa riga è esposta a ub (almeno per le mie conoscenze):

cout<<"Nome : "<<p[n].nome<<" \t"<<p[n].cognome<<" \t"<<p[--n].voto<<endl;

[Scara95]

Piuttosto

int sum(const struct tipo1 *p, n, acc) {
  if(n == 0)
    return acc;
  else
    return sum(p, n-1, acc + p[n-1]);
}

double media(const struct tipo1 *p, n) {
  return sum(p, n, 0) / ((double)n);
}

[Samuele_70]

Quanta enfasi scara , l'unico rischio nel mio codice, così come nei tuoi è una vulnerabilità del tipo division by zero, ma facilmente ovviabile.

Piuttosto

int sum(const struct tipo1 *p, n, acc) {
  if(n == 0)
    return acc;
  else
    return sum(p, n-1, acc + p[n-1]);
}

double media(const struct tipo1 *p, n) {
  return sum(p, n, 0) / ((double)n);
}

p è un puntatore a strutture tipo1, forse volevi scrivere acc + p[n-1].voto

[Scara95]

Vabbè, quell'errore era banale.

Il punto non era che il tuo codice non funziona. (a parte quello che secondo me è ub)
Il punto è che ha side effects.
Mantiene uno stato.

Il risultato non dipende solo dai parametri passati

Esempio:
Supponiamo di trovarci in ambiente concorrente (questo ovviamente non è c++, ma un pseudolinguaggio):

double zero = 0.0;
spawn {cout << media(p1, 4, zero) << endl;}
spawn {cout << media(p2, 4, zero) << endl;}

Supponendo di conoscere p1, p2 e che cout sia sincronizzato in modo da dare un output prevedibile (al più si scambia l'ordine delle righe),
sai dirmi l'output?

Il tuo codice è antieducativo. Inoltre mantenere uno stato esterno già di per sé va contro i principi della programmazione "funzionale".

Aggiungo che mentre le mie due implementazioni (corrette a meno di un .voto) sono ottimizzabili in un ciclo in quanto ricorsive in coda (tail recursive), la tua non lo è e si mangerà lo stack.

Insomma, ci sono molti buoni motivi per evitare un implementazione simile. Sicuramente un professore che cerca di insegnare a pensare ricorsivamente la considererebbe errata (a livello pratico).

In sostanza la tua implementazione non da nessun vantaggio ma da molti problemi.
La mia di certo non da vantaggi rispetto a un'implementazione nativa con un for, ma non da neanche problemi. (sarebbe trascurabile anche il "mangiarsi lo stack" a livello educativo, ma non il resto)

[Samuele_70]

Convengo che il decremento a n, era meglio metterlo da solo in una riga precendente e non dove invece l'ho messo io, non che non funzioni così com'è, ma solo perché non è una pratica sempre consigliabile, in altre circostanze o con altri compilatori, non è affatto detto che sia sempre la prima istruzione ad essere valutata. Si potrebbe ottenere comportamento indefinito appunto

[Scara95]

Si, vabbè, ma anche se avessi scritto n--; la riga prima e n lì il mio giudizio non sarebbe cambiato.