Verifichiamo l'efficienza del calcolo dei numeri di Fibonacci

L'esercitazione non guidata della scorsa lezione prevedeva di calcolare l'n-esimo numero di Fibonacci utilizzando una funzione ausiliaria, implementata in modo ricorsivo e iterativo.

Alcuni di voi hanno probabilmente gia' notato la differenza nel tempo di esecuzione delle due procedure.

Verifichiamo il tempo necessario per calcolare lo stesso numero di Fibonacci utilizzando le due diverse implementazioni della funzione ausiliaria.


Scriviamo due programmi, FibIte e FibRic, per calcolare i numeri di Fibonacci in maniera iterativa e ricorsiva

/*
  Calcola il numero di Fibonacci, ricorsivamente
*/

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

int F(int);

int main () {
                      
  int numero;

  printf("Immetti un numero maggiore o uguale a 0: \n");
  scanf("%d",&numero);
  while (numero<0) {
  printf("Il numero deve essere >0. Ripeti l'inserimento\n");
  scanf("&d",&numero);
  }
  printf("F(%d) = %d\n",numero,F(numero));

  return EXIT_SUCCESS;

}

int F(int n) {
  int risultato; 

  if ( n < 2 ) 
    risultato = n; 
  else
    risultato = F(n-1) + F(n-2); 
                                                                       
return risultato; 
}
 



/*
  Calcola il numero di Fibonacci, iterativamente
*/

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

int F(int);

int main () {
                      
  int numero;

  printf("Immetti un numero maggiore o uguale a 0: \n");
  scanf("%d",&numero);
  while (numero<0) {
  printf("Il numero deve essere >0. Ripeti l'inserimento\n");
  scanf("&d",&numero);
  }
  printf("F(%d) = %d\n",numero,F(numero));

  return EXIT_SUCCESS;

}

int F(int n) {
 int i,F_meno2=0,F_meno1=1,risultato; 

  if ( n<2 ) 
    risultato = n; 
  else
    for ( i=2 ; i<=n ; i++ ) {
      
      risultato = F_meno1 + F_meno2;

      F_meno2 = F_meno1; 
      F_meno1 = risultato;
    }
                                                                      
  return risultato; 
}



A tale scopo possiamo usare i comandi

> time ./FibRic

> time ./FibIte

per ottenere il tempo di esecuzione.
Alla fine compariranno tre valori, di cui quello riferito come user è il più informativo: real si riferisce al tempo intercorso tra il lancio del programma e la sua terminazione; user al tempo di uso effettivo della CPU; e sys al tempo di uso effettivo della CPU da parte del sistema.

Come mai la versione ricorsiva e' meno efficiente?

La spiegazione risiede nel fatto che la formula ricorsiva impiega una doppia ricorsione che causa ripetute invocazioni per il calcolo dello stesso valore.

Ad esempio, per calcolare F(5), verranno invocate ricorsivamente due istanze (indipendenti tra loro) per il calcolo rispettivamente di F(4) e di F(3). A sua volta il calcolo di F(4) richiederà il calcolo di F(3) e di F(2), mentre quello di F(3) richiederà il calcolo di F(2) e di F(1). Già a questo punto dovrebbe essere evidente che si eseguono molte più chiamate di quelle strettamente necessarie, perché si vuole calcolare più volte lo stesso valore (ad esempio, F(3) o F(2)).

La versione iterativa invece calcola ogni valore esattamente una volta.

Imparando a programmare funzioni ricorsive, può essere utile osservare quali (e quante) chiamate vengono effettuate dall'algoritmo, in modo da valutare l'efficienza della soluzione proposta.

A questo scopo basta aggiungere un opportuno comando di stampa all'inizio di ogni funzione per visualizzare il nome della funzione e gli argomenti sui quali è stata invocata.

Nell'esempio riportato sotto l'istruzione di stampa è evidenziata in colore blu.

/*
  Calcola il numero di Fibonacci, ricorsivamente
*/

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

int F(int);

int main () {
                      
  int numero;

  printf("Immetti un numero maggiore o uguale a 0: \n");
  scanf("%d",&numero);
  while (numero<0) {
  printf("Il numero deve essere >0. Ripeti l'inserimento\n");
  scanf("&d",&numero);
  }
  printf("F(%d) = %d\n",numero,F(numero));

  return EXIT_SUCCESS;

}

int F(int n) {
  int risultato; 

  printf("F(%d)\n",n);
  if ( n < 2 ) 
    risultato = n; 
  else
    risultato = F(n-1) + F(n-2); 
                                                                       
return risultato; 
}


Come esercizio, si provi a compilare ed eseguire il programma per calcolare F(7): verrà stampata una lista di 40 invocazioni, quando chiaramente il calcolo ottimizzato richiederebbe semplicemente il calcolo di 8 valori (F(0), F(1), ... , F(7))!


Passaggio di Array come parametri di una funzione

Il passaggio di array a funzioni richiede una certa cautela. Per prima cosa, non è sensato definire una funzione che accetta array di dimensione prefissata, dato che questo costringerebbe a definire funzioni diverse che realizzano lo stesso scopo ma che richiedono array di lunghezze diverse come parametro. Conseguenza immediata è che quando passiamo un array dobbiamo anche passare la sua dimensione come ulteriore parametro della funzione.

Ad esempio, il prototipo di una funzione per il calcolo della somma di tutti gli elementi di un generico array di double dovrà essere: 

double somma(double[], int);
Notare che nel primo parametro, di tipo array di double, la dimensione non viene specificata (nelle parentesi quadre non compare alcun valore).

La definizione della funzione dovrà invece sfruttare il secondo parametro per capire quale sia il limite dell'array:

double somma(double a[], int n) {
    int i;
    double totale=0.0;

    for ( i=0 ; i<n ; i++ )
        totale += a[i];

    return totale;
}
La funzione main potrà invocare la funzione somma su array di qualsiasi dimensione. Provate a compilare ed eseguire il codice completo riportato sotto.

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

#define L1  10
#define L2  50
#define L3 100

double somma(double[], int);

int main () {
             
  double piccolo[L1];
  double medio[L2];
  double grande[L3];
  int i;
         
  for ( i=0 ; i<L1 ; i++ )
        piccolo[i]=1.0;

  for ( i=0 ; i<L2 ; i++ )
        medio[i]=1.0;

  for ( i=0 ; i<L3 ; i++ )
        grande[i]=1.0;

  printf("somma(piccolo,L1) = %f\n",somma(piccolo,L1));
  printf("  somma(medio,L2) = %f\n",somma(medio,L2));
  printf(" somma(grande,L3) = %f\n",somma(grande,L3));

  return EXIT_SUCCESS;

}

double somma(double a[], int n) {
  int i;
  double totale=0.0;

  for ( i=0 ; i<n ; i++ )
      totale += a[i];

  return totale;
}


Nota: Gli array vengono allocati in porzioni contigue della memoria. Quando un array deve essere passato ad una funzione, invece di copiarne tutti gli elementi in una nuova variabile locale di tipo array, quello che succede è che l'indirizzo base dell'array viene passato per valore. Di fatto questo corrisponde ad un passaggio per indirizzo dell'array, dato che eventuali modifiche si ripercuoteranno sull'array originale. Ad esempio, possiamo definire una funzione che inizializza tutti gli elementi di un generico array di double ad uno stesso valore v nel seguente modo:

void inizializza(double a[], int n, double v) {
    int i;

    for ( i=0 ; i<n ; i++ )
        a[i]=v;
}


Torna alla HomePage del corso