In breve: Due modi diversi per risolvere problemi ripetitivi: ripetere con un ciclo oppure richiamare la funzione su se stessa.
Cosa significa risolvere un problema "ripetendo"
In informatica molti problemi si risolvono ripetendo gli stessi passi. Pensa a salire una scala: fai un gradino, poi un altro, fino in cima.
Per dire al computer di ripetere abbiamo due strade principali. La prima si chiama iterazione. La seconda si chiama ricorsione.
Entrambe arrivano allo stesso risultato. Cambia il modo di pensare al problema.
La logica iterativa
L'iterazione usa un ciclo. Il programma ripete le istruzioni finché una condizione resta vera.
I cicli più comuni sono for e while. Servono per contare, scorrere una lista o cercare un dato.
Esempio quotidiano: contare i gradini mentre sali. A ogni passo aggiungi uno e controlli se sei arrivato.
Il vantaggio dell'iterazione è che usa poca memoria. Il computer tiene solo il valore corrente del contatore.
La logica ricorsiva
Nella ricorsione una funzione richiama se stessa su un problema più piccolo. Si ferma quando incontra un caso base.
Il caso base è la condizione di stop. Senza di esso la funzione girerebbe per sempre.
Esempio quotidiano: aprire scatole dentro scatole. Apri la prima, trovi un'altra scatola, ripeti finché non trovi un oggetto.
La ricorsione è elegante per problemi che si dividono in parti simili. Però usa più memoria per ogni chiamata.
Esempi: come si fa
Calcolare il fattoriale di un numero in forma iterativa.
def fattoriale_iter(n):
risultato = 1
for i in range(1, n + 1):
risultato = risultato * i
return risultato
Lo stesso calcolo in forma ricorsiva.
def fattoriale_ric(n):
if n == 0:
return 1
return n * fattoriale_ric(n - 1)
Entrambe le funzioni danno lo stesso risultato. La prima usa un ciclo, la seconda chiama se stessa.
Una regola pratica: usa l'iterazione per problemi semplici e ripetitivi. Usa la ricorsione quando il problema si scompone in sotto-problemi uguali.
Parole difficili
- Iterazione: ripetizione di istruzioni tramite un ciclo controllato da una condizione.
- Ricorsione: tecnica in cui una funzione chiama se stessa su dati più piccoli.
- Caso base: condizione che ferma la ricorsione e restituisce un valore diretto.
- Ciclo: blocco di codice che si ripete più volte secondo una regola.
- Funzione: gruppo di istruzioni con un nome, richiamabile più volte.
- Fattoriale: prodotto di tutti i numeri interi positivi fino a un numero dato.
Riferimenti
- Norma: Riordino degli istituti tecnici
- Obiettivo formativo coperto: ob.tecnico-informatica-telecomunicazioni.informatica.cl3.logica-iterativa-ricorsiva.01