User Tools

Site Tools


appunti3s:ricorsione
Torna alla pagina iniziale > indice

Cenni alla ricorsione

Premessa

Un programma che ripete più volte la stessa operazione, in teoria, può essere scritto secondo due approcci:

Esempio del fattoriale di un intero N

Chi volesse utilizzare l'approccio della iterazione per spiegare come si calcola il fattoriale, potrebbe usare le seguenti parole:

  • ripetere per i da 1 a N
    • moltiplicare tra loro tutti i valori di i

Chi volesse utilizzare l'approccio della ricorsione, invece, potrebbe dire:

  • moltiplicare N * (N-1)
    • moltiplicare il risultato precedente per (N-2)
      • moltiplicare il risultato precedente per (N-3)
        • … e così via…
          • fino a 1

Nell'approccio ricorsivo, le parole “e così via” descrivono l'espressione della soluzione in termini di uso quotidiano. Quindi, sebbene, in teoria, ogni problema possa essere risolto usando entrambi gli approcci, vi sono alcuni problemi che si prestano ad essere risolti più facilmente in un modo piuttosto che nell'altro.

Condizioni

Per risolvere un problema con una ricorsione è necessario:

  • esprimere la soluzione del passo generico i nei termini del passo precedente (i-1), ad esempio:
     fattoriale(i) = i*fattoriale(i-1); // esprime il problema nei termini di se stesso
  • esprimere una condizione di terminazione, ad esempio:
    fattoriale(0) = 1;
41.cpp
// calcolo del fattoriale
#include <iostream>
int main()
{ 
  int numero, fattoriale=1;
  std::cout << "Inserire un numero intero positivo: " << std::endl;
  std::cin >> numero;
 
  for (int i=1; i<=numero; i++)
    fattoriale = numero*fattoriale;
 
  std::cout << "Il fattoriale di " << numero << " vale " << fattoriale << std::endl;
  return 0;
}

Questo appena visto era l'approccio iterativo, si può vedere anche la pagina

ricorsione

appunti3s/ricorsione.txt · Last modified: 2020/06/08 22:20 by 127.0.0.1