[C] aiuto

[Manugal]

Ciao!

Oggi mi hanno spiegato alcune cose sulla ricorsività e come esempio è stato fatto quello della successione di Fibonacci. Praticamente per avere un numero minore di chiamate alla funzione rispetto all'implementazione classica, abbiamo implementato un algoritmo che memorizzasse in un array i valori già calcolati. Questo è l'algoritmo:

#include <stdio.h>
#include <stdlib.h>

int fib(int);
int valori[100]={0};

int main(void){

   int n=5,ris;
   ris=fib(n);
   printf("%d", ris);
   return 0;
}

int fib(int n){
   if(valori[n]>0)
      return valori[n];
   if(n==0)
      valori[n]=0;
   if(n==1)
      valori[n]=1;
   else
      valori[n]=fib(n-1)+fib(n-2);
      return valori[n];
}

Quello che non riesco a capire è come si comporta l'indice dell'array (dato che è uguale a n). Infatti eseguendo questo programma (che mi dovrebbe restituire 5), mi restituisce 24042062. Come mai? Grazie.

[Ziosilvio]

Il programma funziona a condizione che tutte le componenti del vettore valori siano inizializzate a zero prima della prima chiamata a fib.
Ora, l'istruzione:

int valori[100]={0};

dichiara valori come un array statico di 100 elementi, e poi inizializza a zero la sua prima componente: le altre, non vengono inizializzate e il loro valore al momento della prima chiamata a fib può essere qualunque cosa.
Per inizializzare a zero tutte le componenti del vettore valori, devi o usare un ciclo for, o scrivere "parentesi graffa aperta, zero, virgola, zero, virgola, ..., zero, virgola, zero, parentesi graffa chiusa, punto e virgola" a destra dell'uguale, dove gli zeri sono tanti quante le componenti del vettore.

[Qu@ker]

Originariamente inviato da Ziosilvio

Ora, l'istruzione:

int valori[100]={0};

dichiara valori come un array statico di 100 elementi, e poi inizializza a zero la sua prima componente: le altre, non vengono inizializzate e il loro valore al momento della prima chiamata a fib può essere qualunque cosa.

Sbagliato. A norma di standard, quell'istruzione e' corretta (tutti gli elementi dell'array sono inizializzati a 0, vedi ad es. qui).

@Manugal

Nel programma c'e' un evidente errore logico:

   if(n==0)
      valori[n]=0;
   else if(n==1)
      valori[n]=1;
   else
      valori[n]=fib(n-1)+fib(n-2);

[Manugal]

Ah grazie Qu@ker proverò a vedere se hai ragione

Però volevo sapere, dato che fib chiama se stessa più di una volta, l'indice dell'array come si comporta. Quello non riesco a capirlo.

[Ziosilvio]

Originariamente inviato da Qu@ker

A norma di standard, quell'istruzione e' corretta (tutti gli elementi dell'array sono inizializzati a 0, vedi ad es. qui).

'Azz... è vero!
Kernighan&Ritchie, edizione italiana Jackson Libri, pagina 288.
Chiedo perdono.