Funzione Ricorsiva in C

[nasio91]

Salve a tutti, mi sto affacciando alla programmazione in C da un po' di tempo, ma non riesco a capire come si faccia una funzione ricorsiva, fra gli esempi portava il calcolo del fattoriale, e lì qualcosina c'ho capito, ma del tipo calcolare la somma di un array di interi mi sembra una cosa criptica

Qualcuno di buon cuore può darmi una mano?

[Simonex84]

Per esempio

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

"A" è il vettore
"n" il numero di elementi

La logica è che la somma di un vettore è la somma del primo elemento più la somma del restante pezzo, la somma del restante peezzo, è la somma del primo elemento più la somma del restante pezzo, e così via.... finchè sei arirvato alla fine (return 0) che corrisponde al valore dell'elemento dopo la fine del vettore

[nasio91]

Originariamente inviato da Simonex84

Per esempio

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

"A" è il vettore
"n" il numero di elementi

scusa la domanda da tremendo ignorante, credo già di stare per sparare una stronzata, ma sbagliando si impara

return A[n]+somma(A,n-1)

vuol dire prendere l'elemento di A puntato da n e richiamare la funzione somma che andrà a prendere l'elemento n-1 di A?

[Simonex84]

Originariamente inviato da nasio91

scusa la domanda da tremendo ignorante, credo già di stare per sparare una stronzata, ma sbagliando si impara

return A[n]+somma(A,n-1)

vuol dire prendere l'elemento di A puntato da n e richiamare la funzione somma che andrà a prendere l'elemento n-1 di A?

n quando richiami la funzione indica il numero di elementi, all'interno della funziona viene usato anche come indice.

Leggi l'EDIT che ho aggiunto sopra

[WarDuck]

Originariamente inviato da Simonex84

Per esempio

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

"A" è il vettore
"n" il numero di elementi

La logica è che la somma di un vettore è la somma del primo elemento più la somma del restante pezzo, la somma del restante peezzo, è la somma del primo elemento più la somma del restante pezzo, e così via.... finchè sei arirvato alla fine (return 0) che corrisponde al valore dell'elemento dopo la fine del vettore

Tre appunti:

1) Non controlli se l'indice è negativo (conviene passare un unsigned)
2) A[n] provoca un buffer overflow, in C gli indici degli array vanno da 0 a N-1.
3) Per le variabili è meglio usare nomi con lettere minuscole

int somma(int a[], size_t n)
{
   if (n == 0) return 0;

   return a[n-1] + somma(a, n-1);
}

[Simonex84]

Originariamente inviato da WarDuck

Tre appunti:

1) Non controlli se l'indice è negativo (conviene passare un unsigned)
2) A[n] provoca un buffer overflow, in C gli indici degli array vanno da 0 a N-1.
3) Per le variabili è meglio usare nomi con lettere minuscole

int somma(int a[], size_t n)
{
   if (n == 0) return 0;

   return a[n-1] + somma(a, n-1);
}

ma se do a nasio91 una soluzione perfetta poi lui non deve più fare nulla

a parte gli scherzi l'ho buttato giù al volo prima di andare a pranzo, comunque anche la tua non va bene perchè così non sommi l'elemento in prima posizione a(0)

così invece dovremmo esserci

int somma(int a[], int n)
{
   if (n < 0) return 0;

   return a[n-1] + somma(a, n-1);
}

[WarDuck]

Originariamente inviato da Simonex84

ma se do a nasio91 una soluzione perfetta poi lui non deve più fare nulla

a parte gli scherzi l'ho buttato giù al volo prima di andare a pranzo, comunque anche la tua non va bene perchè così non sommi l'elemento in prima posizione a(0)
...

Aspetta eh... fammici pensare .

Quando n = 1 prendo a[0], quindi in teoria dovrebbe funzionare.

La cosa più semplice per capirlo è considerare che n indica il numero di elementi da sommare.

Quindi mi sa che la mia è ancora valida .

Cmq spero che i nostri ragionamenti aiutino nasio a capire.

[M@Rk0]

Originariamente inviato da WarDuck

Aspetta eh... fammici pensare .

Quando n = 1 prendo a[0], quindi in teoria dovrebbe funzionare.

La cosa più semplice per capirlo è considerare che n indica il numero di elementi da sommare.

Quindi mi sa che la mia è ancora valida .

Cmq spero che i nostri ragionamenti aiutino nasio a capire.

quando n==1 chiami somma(a,0)
ma in quest'ultima chiamata fai il check if n==0 e restituisci subito 0, non il contenuto di a[0]
quindi correggendo (io non lo scriverei mai così) sarebbe:

int somma(int a[], size_t n)
{
   if (n == 0) return a[n];

   return a[n-1] + somma(a, n-1);
}

resta il fatto che la somma degli elementi di un array si potrebbe senza problemi calcolare iterativamente, aggirando a monte il problema

[wingman87]

Quando n=1 return a[n-1] + somma(a, n-1) cioè a[0] + somma(a, 0) cioè a[0] + 0 quindi è corretto

[Simonex84]

Originariamente inviato da M@Rk0

resta il fatto che la somma degli elementi di un array si potrebbe senza problemi calcolare iterativamente, aggirando a monte il problema

in questo esempio usare la ritorsione è una forzatura a scopo didattico (userei anche io un ciclo), però è bene prenderci la mano perché una tecnica di programmazione molto utile

[WarDuck]

Originariamente inviato da M@Rk0

quando n==1 chiami somma(a,0)
ma in quest'ultima chiamata fai il check if n==0 e restituisci subito 0, non il contenuto di a[0]
...

E dev'essere così.

L'ultimo passo rimane: a[0] + 0, che quindi è corretto .

Originariamente inviato da M@Rk0

resta il fatto che la somma degli elementi di un array si potrebbe senza problemi calcolare iterativamente, aggirando a monte il problema

Chiaro, ma l'autore del thread voleva delucidazioni sulla versione ricorsiva.

[oNaSsIs]

Al di là della questione sugli indici del vettore restituito, il problema credo sia un altro, ovvero che ti concentri troppo sull'aspetto implementativo e poco sull'aspetto matematico. Devi provare a scrivere la funzione ricorsiva prima in termini matematici e poi vedrai che tradurla in qualsiasi linguaggio di programmazione diventa un problema banale.

Il fattoriale, che già ti è chiaro può essere definito come

factorial 0 = 1
factorial n = n * factorial (n - 1)

Quello che ho scritto è codice Haskell, ma ho fatto questa scelta semplicemente perché è un linguaggio molto ad alto livello con una notazione vicinissima a quella matematica.
Il codice significa la seguente cosa. Il fattoriale di 0 è uguale 1, mentre il fattoriale di un generico numero n è uguale a n moltiplicato il fattoriale di n-1. Mi sembra piuttosto semplice da interpretare.
Personalmente sono abituato a scrivere prima il caso generale (la seconda riga dell'esempio) e poi il caso base (la prima riga). Questo perché in pratica il caso base serve come condizione di arresto della ricorsione. Ripeto, è solo un consiglio e non una regola.

Il tuo problema di calcolare la somma di un vettore può quindi essere risolto come:

sum []     = 0
sum (head:tail) = head + sum tail

Considerando che (head:tail) scompone il vettore affinché head contenga la testa del vettore, ovvero il primo elemento, e tail la sua coda, ovvero tutti i restanti elementi, nel seguente esempio abbiamo:

vettore = [3,5,6,7,8,2]
quindi
head = 3
tail = [5,6,7,8,2]

La funzione ricorsiva della sommatoria di un vettore, può quindi essere pensata nel caso generale come la somma del primo elemento più la sommatoria della parte restante del vettore. Il caso base ovviamente è quello della lista vuota la cui somma assumiamo sia 0.
Questo è quello che dovrebbe essere il tuo modo di pensare, ad alto livello aiutandoti con una notazione vicina a quella matematica.

Ora purtroppo per te implementare questa funzione ricorsiva in C non può essere fatto in maniera diretta usando i vettori, quindi quello che si fa è usare un contatore che scorre il vettore durante la ricorsione.
Usando uno pseudo-codice simile a quello usato finora, ma più vicino al C:

sum vect index = 
    if index < 0
        return 0
    else
        return vect[index] + sum vect (index-1)

Ho fatto questo giro lunghissimo e forse un po' complicato per mostrarti quello che dovrebbe essere il tuo modo di ragionare.
Per questo problema, come sottolineato anche da altri utenti, la ricorsione è un po' una forzatura, soprattutto perché l'implementazione in C con vettori forza l'uso di un contatore.
Al contrario, usando un altro linguaggio che supporta nativamente le liste il codice sarebbe risultato pressoché identico a quello che ho scritto prima in Haskell.
Ad esempio in Python:

def sumList(list):
    if len(list)==0:
            return 0
    else:
            return list[0] + sumList(list[1:])

Come vedi, se trascuri la sintassi, la logica è esattamente la stessa. Nota che list[1:] è l'equivalente del tail definito in precedenza.

[M@Rk0]

Originariamente inviato da wingman87

Quando n=1 return a[n-1] + somma(a, n-1) cioè a[0] + somma(a, 0) cioè a[0] + 0 quindi è corretto

Originariamente inviato da WarDuck

E dev'essere così.
L'ultimo passo rimane: a[0] + 0, che quindi è corretto .

si è vero, avevo letto male

Originariamente inviato da Simonex84

in questo esempio usare la ritorsione è una forzatura a scopo didattico (userei anche io un ciclo), però è bene prenderci la mano perché una tecnica di programmazione molto utile

Originariamente inviato da WarDuck

Chiaro, ma l'autore del thread voleva delucidazioni sulla versione ricorsiva.

altrettanto chiaro che fosse una battuta, o quando leggete non parsificate le emoticon? [segue faccina "asd"]

[vbextreme]

int somma(int v[], int n)
{
    return ( --n ) ? v[n] + somma(v,n) :  v[n];
}

[Simonex84]

Originariamente inviato da vbextreme

int somma(int v[], int n)
{
    return ( --n ) ? v[n] + somma(v,n) :  v[n];
}

per utente alle prime armi io userei un codice più "semplice" e meno sintetico

[nasio91]

Originariamente inviato da Simonex84

per utente alle prime armi io userei un codice più "semplice" e meno sintetico

Yep è un po criptica come codice... Grazie comunque a tutti ragazzi! Chiarissimi e disponibili

[sottovento]

Originariamente inviato da vbextreme

int somma(int v[], int n)
{
    return ( --n ) ? v[n] + somma(v,n) :  v[n];
}

Ovviamente assumendo che n > 0. Per n == 0 va in crash.

[sottovento]

Originariamente inviato da Simonex84

così invece dovremmo esserci

int somma(int a[], int n)
{
   if (n < 0) return 0;

   return a[n-1] + somma(a, n-1);
}

Andrai in crash per n == 0. Quella che aveva scritto warduck era invece corretta:

int somma(int a[], size_t n)
{
   if (n == 0) return 0;

   return a[n-1] + somma(a, n-1);
}