La serie di Fibonacci, con una funzione ricorsiva

Vediamo ora un esempio di uso della ricorsione. Implementiamo una funzione ricorsiva che stampa gli elementi della serie di Fibonacci fino a un certo valore. La serie di Fibonacci è una sequenza di numeri interi, i cui primi due sono 1 e 1. Ogni successivo elemento della sequenza si ottiene sommando i precedenti due elementi. Per esempio, il terzo numero della sequenza è la somma del primo e del secondo, ossia vale 2. Quindi, i primi tre elementi della sequenza sono 1 1 2. Il quarto si ottiene sommando gli ultimi due, cioè 1 e 2, e quindi vale 3. Dato che ora abbiamo 1 1 2 3, il quinto si ottiene sommando gli ultimi due, e quindi vale 2+3=5.

Possiamo quindi realizzare una funzione ricorsiva che prende come argomenti gli ultimi due elementi calcolati fino ad ora, calcola la somma, la stampa (se è minore del massimo prefissato), e poi fa la chiamata ricorsiva.

Per quello che riguarda la chiamata ricorsiva, occorre tenere presente che la funzione deve prendere come argomenti gli ultimo due valori calcolati. Questo significa che il valore nuovo che abbiamo calcolato è in effetti l'ultimo valore calcolato, mentre quello che prima era l'ultimo ora è il penultimo, semplicemente perchè ora ne abbiamo trovato uno nuovo.

La funzione deve avere tre parametri, che sono gli ultimi due valori calcolati, e poi il limite (quello che dice a che punto ci dobbiamo fermare). Come nome per le prime due variabili usiamo i nome penultimo e ultimo, che dice appunto quali sono gli ultimi due valori trovati. Per il valore massimo da calcolare usiamo un parametro che chiamiamo limite.

La funzione cosa fa? Calcola il prossimo valore della serie, e questo si ottiene semplicemente sommando i due ultimi valori calcolati. Mettiamo questo nuovo valore trovato in una variabile, per esempio usiamo il nome di variabile nuovo. Si confronta il valore trovato con il limite: se il limite è stato raggiunto oppure superato, si termina, dato che abbiamo raggiunto il massimo valore che andava calcolato. Se invece il massimo non è stato raggiunto, stampiamo l'ultimo valore calcolato. A questo punto, le variabili penultimo, ultimo e nuovo contengono in effetti gli ultimi tre valori della serie che abbiamo trovato. Si noti che il penultimo valore trovato si trova in ultimo, mentre l'ultimo valore trovato si trova in nuovo. La variabile ultimo conteneva l'ultimo valore trovato, ma ora ne abbiamo trovato un altro, per cui la variabile ora contiene in effetti il penultimo valore.

Per far funzionare il tutto, occorre ora fare la chiamata ricorsiva per calcolare i successivi valori. Dal momento che il limite è lo stesso di quello che abbiamo ricevuto, bisogna solo capire cosa dobbiamo mettere come primi due argomenti della chiamata ricorsiva. Dato che la funzione riceve gli ultimi due valori trovati, e questi stanno nelle variabili ultimo e nuovo, la chiamata ricorsiva deve passare come parametri ultimo, nuovo e limite. La funzione che si ottiene è qui sotto.

void fibonacciRicorsiva(int penultimo, int ultimo, int limite) {
  int nuovo;

  nuovo=penultimo+ultimo;

  if(nuovo<limite) {
    printf("%d ", nuovo);

    fibonacciRicorsiva(ultimo, nuovo, limite);
  }
}

Occorre ora capire in che modo la funzione va chiamata. Occorre dare come primi due parametri 1 e 1, dal momento che questi sono i primi due elementi della sequenza. Il terzo parametro è semplicemente il limite che viene dato. Volendo realizzare una funzione che stampa gli elementi della serie fino al limite, quello che occorre fare è stampare i primi due elementi della serie, e poi chiamare la funzione ricorsiva per stampare gli altri. Quindi, occorre realizzare una funzione come quella qui sotto.

void fibonacci(int limite) {
  printf("1 ");
  printf("1 ");

  fibonacciRicorsiva(1, 1, limite);
}

Il programma completo fiboric.c contiene un programma principale che riceve il limite come argomento, e fa una semplice chiamata alla funzione di sopra.

Vediamo ora la simulazione della esecuzione del programma quando si passa 6 come limite alla funzione fibonacci. Non ci interessa come è fatto il record di attivazione di main. Guardiamo solo i record di attivazione successivi. Dal momento che main chiama fibonacci passando il valore 6, nel record di attivazione della funzione fibonacci c'è il valore 6 nella variabile (parametro formale) limite.

Viene ora chiamata la funzione fibonacciRicorsiva. A questa funzione si passano come argomenti i valori 1, 1 e il valore di limite, ossia 6. Questo significa che la chiamata fibonacciRicorsiva(1, 1, limite); è equivalente a:

fibonacciRicorsiva(1, 1, 6);

La intestazione della funzione è:

void fibonacciRicorsiva(int penultimo, int ultimo, int limite)

Questo siginifica che i valori dei parametri formali penultimo, ultimo e limite valgono 1, 1 e 6. Si esegue poi la somma, che si mette in nuovo. A questo punto, lo stack dei record di attivazione è il seguente.

Dato che nuovo è minore di limite, si esegue la stampa e la chiamata ricorsiva. La chiamata ricorsiva crea un nuovo record di attivazione, in cui si trovano i parametri formali. Per capire cosa ci va messo in questi parametri, occorre seguire questa regola:

1. si scrive la chiamata ricorsiva mettendo i valori effettivi degli argomenti. Dato che la chiamata ricorsiva è fibonacciRicorsiva(ultimo, nuovo, limite), si vanno a vedere i valori delle variabili nel record corrente, ossia quello più in alto (nello stato attuale, lo stack è quello della figura sopra). Dato che ultimo vale 1, mentre nuovo vale 2 e limite vale 6, i tre valori nella chiamata ricorsiva sono:

   fibonacciRicorsiva(1, 2, 6);
   

2. si scrive la intestazione della funzione:

   void fibonacciRicorsiva(int penultimo, int ultimo, int limite)
   

3. in ogni variabile della intestazione si mette il corrispondente valore che sta fra parentesi nella chiamata ricorsiva. Nel nostro caso, dal confronto si vede che in penultimo ci va 1, in ultimo ci va 2, mentre in limite ci va 6.

Abbiamo quindi la situazione seguente (nella chiamata ricorsiva, si calcola il valore di nuovo come somma di penultimo e ultimo).

Si noti che la regola scritta sopra (valutare gli argomenti sulla base dei valori delle variabili nell'elemento dello stack affiorante) va presa alla lettera. In particolare, dalla regola si capisce che i valori delle variabili nella nuova chiamata ricorsiva non sono necessariamente uguali a quelli del record sottostante. In particolare, questo avviene solo se il valore di una variabile viene passato direttamente nella chiamata ricorsiva. Inoltre, le variabili locali che non sono i parametri formali della funzione, hanno un valore iniziale indefinito (non si può assumere che abbiano inizialmente gli stessi valori che si trovano nel record precedente).

Dato che ora nuovo vale meno di limite, si stampa e si esegue nuovamente la chiamata ricorsiva. Qui seguiamo ancora la stessa regola: la chiamata è:

fibonacciRicorsiva(ultimo, penultimo, limite);

Si valutano le variabili, guardando l'ultimo record di attivazione.

fibonacciRicorsiva(2, 3, 6)

Dal confronto con la intestazione della funzione, si capiscono i valori dei parametri nel nuovo record di attivazione (che sono appunto 2, 3 e 6).

A questo punto, si ripete tutto di nuovo. Il valore calcolato per nuovo è ancora minore del valore di limite, per cui si stampa il numero, e si effettua la chiamata ricorsiva. Per i valori dei parametri formali nella nuova chiamata ricorsiva, si segue ancora la regola si sopra, per cui si vede che i valori iniziali di penultimo, ultimo e limite sono 3, 5 e 6.

Il calcolo del valore di nuovo produce 8, che è superiore al valore di limite, per cui la funzione termina senza fare né la stampa né la chiamata ricorsiva. A questo punto si torna ad eseguire quello che mancava della funzione chiamante. In questo caso, la chiamata ricorsiva era l'ultima istruzione, per cui tutte le funzioni terminano, e si ritorna direttamente al programma principale, deallocando tutti i record di attivazione.