Differences

This shows you the differences between two versions of the page.

--- appunti3s:ricorsione [2018/05/03 16:29]
profpro
+++ appunti3s:ricorsione [2020/06/08 22:20] (current)
@@ Line 1: / Line 1: @@
+> Torna alla pagina iniziale > [[appunti3s:indice]]
+====== Cenni alla ricorsione ======
+===== Premessa =====
+Un programma che ripete più volte la stessa operazione, __in teoria__, può essere scritto secondo due approcci:
+  * l'iterazione (precedentemente vista in [[appunti3s:tre_strutture#struttura_iterativa]]
+  * la ricorsione
+=====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: <code> fattoriale(i) = i*fattoriale(i-1); // esprime il problema nei termini di se stesso</code>
+   * esprimere una condizione di terminazione, ad esempio: <code>fattoriale(0) = 1;</code>
+<file cpp 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;
+}
+</file>
+Questo appena visto era l'approccio iterativo, si può vedere anche la pagina
+[[olimpiadi:ricorsione]]

Appunti di informatica

User Tools

Site Tools

Differences

Page Tools