next up previous contents index
Next: Quick sort Up: Ordinare un array Previous: Selection sort   Indice   Indice analitico

Funzioni ricorsive

Prima di introdurre il secondo algoritmo di ordinamento, è necessario dire qualche parola sulle funzioni ricorsive. A qualcuno potrà sembrare strano che questo argomento, al quale in molti testi viene data una importanza rilevante, venga relegato in una sottosezione sugli array. Il motivo è il seguente: le funzioni ricorsive sono difficili da assimilare, anche nel loro funzionamento basilare, e non trovano applicazione in nessun argomento contenuto normalmente nei libri di testo di informatica per le Scuole Medie Superiori. Allora perché imporre lo studio di un argomento, se esso presto verrà dimenticato perché difficilmente applicabile ai programmi normalmente presentati? Abbiamo preferito dunque ritardare l'uso delle funzioni ricorsive, trattarle in questa sede e applicarle immediatamente nella prossima sottosezione; successivamente, consideremo materiale di approfondimento la codifica di algoritmi tramite le funzioni ricorsive.

Bene, suscitata una certa curiosità sull'argomento, vediamo cosa esse siano in realtà. Una funzione ricorsiva è una funzione che contiene al suo interno una chiamata a se stessa6.3. Perché? In determinati casi gli algoritmi ricorsivi (e quindi le funzioni ricorsive) sono meglio adatti a modellizzare un problema di quelli iterativi. Il classico esempio è la definizione stessa di fattoriale di un numero intero:

\begin{displaymath}
n! = \left\{\begin{array}{l}
1 \qquad\mathrm{se} \qquad n = ...
...t (n-1)! \qquad\mathrm{se} \qquad n \neq 0
\end{array} \right.
\end{displaymath}

la funzione fattoriale ($!$) è richiamata all'interno della sua definizione stessa, per cui si tratta di un problema intrinsecamente ricorsivo. Vediamo come esso si implementi in C++:

// ex6_3_2.cpp
#include <iostream.h>

int fattRicorsivo (int n) {
  if (n == 0)
    return 1;
  return n*fattRicorsivo (n - 1);
}

void main() {
  cout << "6! = " << fattRicorsivo(6);
}

output:
6! = 720

Cosa succede quando all'interno di main chiamiamo la funzione fattRicorsivo? Viene chiamata la funzione seguente:

fattRicorsivo (6)
la quale non termina perché, siccome non vale 6 == 0, essa chiama la seguente funzione:
fattRicorsivo (5)
che a sua volta chiama la stessa funzione, avente come parametro 4, poi 3, poi 2, poi 1; infine tale funzione chiama la
fattRicorsivo (0)
che, prima fra tutte, ritorna il valore 1. A questo punto si ha la cosiddetta richiusura, ovvero le funzioni cominciano a chiudersi nell'ordine inverso a quelle con il quale sono state chiamate; così il ritorno dell'ultima funzione è 1, poi 1, poi 2, poi 6, poi 24, poi 120 e infine la funzione chiamata nel programma principale torna 720, che è il risultato corretto di $6!$.

Come si può vedere si tratta di un procedimento molto lungo e tortuoso, che tuttavia in certi casi semplifica notevolmente la vita del programmatore, come vedremo tra poco. Prima però presentiamo due semplici esempi di programmi contenenti funzioni ricorsive:


// ex6_3_3
// calcola N termini della successione di Padovan
#include <iostream.h>

int padovan (int n) {
  if (n == 0 || n == 1 || n == 2)
    return 1;
  return padovan(n-2) + padovan(n-3);
}

void main() {
  const int N = 15;
  for (int i = 0; i < N; i++)
    if (i % 5 == 4)
      cout << padovan(i) << "\n";
    else
      cout << padovan(i) << "\t";
}

output:
 1 1 1 2 2
 3 4 5 7 9
 12 16 21 28 37


// ex6_3_4
// calcola l'n-esima potenza intera di un numero reale
#include <iostream.h>

double potRicorsiva (double base, int esponente) {
  if (esponente == 0)
    return 1;
  return base * potRicorsiva (base, esponente - 1);
}

void main() {
  double b;
  int e;
  cout << "base? "; cin >> b;
  cout << "esponente? "; cin >> e;
  cout << "risultato: " << potRicorsiva (b, e);
}

esempio di output:
base? 1.331335
esponente? 4
risultato: 3.14159


next up previous contents index
Next: Quick sort Up: Ordinare un array Previous: Selection sort   Indice   Indice analitico
Claudio Cicconetti
2000-09-06