[C] Esercizio ricorsione

[floppyes]

Ciao a tutti

Devo svolgere il seguente esercizio utilizzando la ricorsione:
Scrivere una funzione ricorsiva (in C) che calcoli la somma degli elementi di un array A[1..n] di n interi.

Ho provato a scriver il seguente codice:

/*
Scrivere una funzione ricorsiva (in C) che calcoli la somma degli elementi di un array A[1..n] di n interi.
*/

#include <stdio.h>

int somma (int vett[], int n);
int main ()
{
   int numeri[4]={2,5,7,9};
   int tot=4;

   printf("%d", somma(numeri,tot));

   printf("\n");
   return 0;
}


int somma (int vett[], int n)
{
   if (n==0)
      return 0;
   else
      return (vett[n]+somma(vett, n-1));
}

Però non capisco come mai non mi venga mai calcolata la somma!

Sapete indicarmi dove sbaglio?

Grazie mille
Ciaoo

[vict85]

Devi fare vett[n-1] perché vett[n] è fuori dall'array.

[floppyes]

Ciao!

Grazie per la risposta, adesso funziona correttamente. Poiché il vettore inizia da 0 bisogna considerare n-1

Un'altra domanda sempre sulla funzione ricorsiva: in questo esercizio mi viene chiesto di calcolare il numero più piccolo all'interno di un array.

Ho scritto anche qui il codice:

int minimo (int vett[], int n);
int main ()
{
   int numeri[]={57,897,6,58};
   int tot=4;

   printf("%d", minimo(numeri,tot));

   printf("\n");
   return 0;
}


int minimo (int vett[], int n)
{
   if (n==0)
         return 0;
   else
      return (vett[n-1]<minimo(vett,n-1));

}

Però anche qui continua a ritornarmi il valore 0. Ho provato allora ha fare una modifica alla funzione ricorsiva, però mi sa che così diventa una funzione normale in quanto utilizzo un if:

int minimo (int vett[], int n)
{
   if (n==0)
         return 0;

   else if (vett[n-1]<minimo(vett,n-2))
      return (vett[n-2]);

   else
      return vett[0];

}

Come potrei fare per calcolare il minimo utilizzando sempre la ricorsione?

Grazie mille
Buona serata
Ciaoo

[vict85]

La presenza di un if non rende una funzione non ricorsiva.

[floppyes]

Ciao!

Quindi nelle funzioni ricorsive devo basarmi tutto sul return.

Ho riscritto la funzione ma non mi stampa ancora il minimo

int minimo (int vett[], int n)
{
   if (n==0)
         return 0;
   else
      return (vett[n-1]<minimo(vett,n-1));

}

Nel caso in cui n sia uguale a zero allora ritorna il valore zero, altrimenti mi ritorna il valore di n-1 nel caso in cui sia minore del successivo, però non funziona.

Grazie
Ciaoo

[vict85]

Questo dovrebbe funzionare

int minimo (int vett[], int n)
{
   if (n==0)
         return 0;
   else
      return (vett[n-1]<minimo(vett,n-1))? vett[n-1] : minimo(vett,n-1));
}

Non ho controllato.

Il punto è che

 (vett[n-1]<minimo(vett,n-1))

ritorna 1 nel caso sia vero e 0 nel caso sia falso. Non ritorna il valore minimo tra di loro.

[hyoukarou]

Cercando il minimo sarebbe più corretto ritornare il massimo degli interi in caso in cui la lista sia vuota:

#include <limits.h>
 
int min(int first, int second)
{
    return first < second ? first : second;
}
 
int minimum(int vect[], int n)
{
    if(n == 0)
        return INT_MAX;
 
    return min(vect[n-1], minimum(vect, n-1));
}

Questo codice va bene sse \(n \geq 0\), supponendo ovviamente di non trovarci di fronte Machiavelli.
Inoltre se la lista fosse vuota dall'inizio non so quanto senso avrebbe ritornare INT_MAX, quindi io preferirei riscriverlo così:

int minimum(int vect[], unsigned int n)
{
    if(n == 0)
    {
        printf("You rascal!");
        exit(-1); // sarebbe più opportuno un'eccezione, ma in C..
    }
    return minimum_(vect, n);
}

int minimum_(int vect[], unsigned int n)
{
    if(n == 1)
        return vect[0];
 
    return min(vect[n-1], minimum(vect, n-1));
}

[vict85]

A quel punto potevi però far che considerare il caso di $n<0$.

[floppyes]

Ciao!

"vict85":Questo dovrebbe funzionare

int minimo (int vett[], int n)
{
   if (n==0)
         return 0;
   else
      return (vett[n-1]<minimo(vett,n-1))? vett[n-1] : minimo(vett,n-1));
}

Non ho controllato.

Il punto è che

 (vett[n-1]<minimo(vett,n-1))

ritorna 1 nel caso sia vero e 0 nel caso sia falso. Non ritorna il valore minimo tra di loro.

Ho provato il codice ma non funziona mi ritorna sempre il valore 0!

Devo provare il codice di hyoukarou ma se il vettore é vuoto allora dovrei ritornare il valore zero, se contiene un solo elemento allora ritorno quello.

Grazie
Ciaoo

[floppyes]

Ciao!

Scusate se ritorno su questo argomento, ma purtroppo non sono ancora riuscito a risolverlo.

Anche con questo codice:

int minimo (int vett[], int n)
{
   if (n==0)
      return 0;
   else
      return (vett[n-1]<minimo(vett,n-1))? vett[n-1] : minimo(vett,n-1);
}

Mi ritorna sempre 0!

Grazie
Ciaoo

[Obidream]

Perché non fare semplicemente in un modo simile, considerando i vari casi?

int minimo(int v[], int n)
{
if(n==1)
    return v[0];
if(n==2)
    if(v[0]<v[1])
        return v[0];
    else
        return v[1];
if (v[0]<minimo(&v[1],n-1))
    return v[0];
else
    return minimo(&v[1],n-1);
}

[floppyes]

Ciao!

Grazie del suggerimento, così funziona alla perfezione.

Ma con funzione ricorsiva si intende una funzione che richiama se stessa, quindi posso comunque utilizzare if o else?
L'importante è che vi sia un richiamo della funzione all'interno di se stesa giusto?

Un'altra domanda riguardo il codice che hai scritto:

   if (v[0]>minimo(&v[1],n-1))

In questo caso utilizzi &v[1] perché vuoi richiamare il valore in posizione 1 del vettore. Non bastava scrivere solamente v[1]?

Grazie
Ciaoo

[claudio862]

"Obidream":Perché non fare semplicemente in un modo simile, considerando i vari casi?

Il caso n=2 è superfluo. Inoltre questa implementazione ha complessità esponenziale (chiami ricorsivamente la funzione 2 volte ad ogni livello). Salva il risultato della prima chiamata:

int minimo(int v[], int n)
{
    if (n == 1) {
        return v[0];
    }

    int m = minimo(&v[1], n - 1);

    if (v[0] < m) {
        return v[0];
    } else {
        return m;
    }
}

[Obidream]

Grazie Claudio è vero, non ci avevo fatto caso...
Comunque &v[1] non passa il valore dell'elemento in prima posizione, ma l'indirizzo

#include <stdio.h>
#include <stdlib.h>
#define MAX_DIM 10

int minimo(int v[], int n)
{
    if (n == 1) {
        return v[0];
    }

    int m = minimo(&v[1], n - 1);

    if (v[0] < m) {
        return v[0];
    } else {
        return m;
    }
}


int main ()
{
int vett [MAX_DIM]={3,6,4,2,8,9,1,5,-3,-1};
printf("Ecco il minimo: %d\n",minimo(&vett[0],MAX_DIM));
return 0;
}

Forse col main scritto in questo modo si capisce di più

P.s array è il nome della variabile della funzione, avevo scritto di fretta

[floppyes]

Ciao!

Grazie per la risposta. Non riesco però a capire come mai vai a richiamare l'indirizzo

Perché il resto del codice è chiaro, se il vettore contiene un solo elemento allora il minimo è per forza il primo elemento, se il numero in posizione 0 è più piccolo del minimo trovato allora mi ritorna il primo valore, altrimenti mi ritorna il minimo.

Però non capisco coma mai si utilizza l'indirizzo!

Grazie
Ciaoo

[claudio862]

In C array e puntatori sono spesso (non sempre) concetti intercambiabili. Un array decade quasi sempre all'indirizzo del primo elemento. Quindi l'indirizzo del secondo elemento rappresenta un array che parte dal secondo elemento. Le espressioni "&v[1]" e "v + 1" sono equivalenti. In generale "&v[n]" è equivalente a "v + n", quindi "&v[0]" è equivalente a "v + 0", cioè a "v".

[floppyes]

Ciao!

Grazie mille per la spiegazione, ora mi è più chiaro

Un ultimo dubbio: una funzione è ricorsiva se richiama se stessa, quindi posso comunque utilizzare if o else, l'importante è che ci sia il richiamo della funzione all'interno di se stessa giusto?

Grazie
Ciaoo

[claudio862]

Sì. Senza if ed else (o equivalenti, come while, ?: ...) non potresti nemmeno scegliere se fare o meno una chiamata ricorsiva, quindi avresti solo due possibilità: nessuna ricorsione, ricorsione infinita.

[floppyes]

Ciao!

Perfetto grazie mille, ora è tutto più chiaro

Grazie
Ciaoo