Follow

Nella scorsa lezione abbiamo visto come funziona la semplice ricorsione applicata a funzioni numeriche. La ricorsione è però molto più potente e ci permette di operari anche con oggetti che non siano solamente numeri.

Diamo quindi ora una definizione di algoritmo ricorsivo meno formale ma che serve a decifrare meglio il problema a livello pratico.

Supponiamo che ci sia una funzione F che risolva un problema su un input P di dimensione N. N può essere il numero di elementi di una lista, il numero di nodi di un grafo o di un albero, il numero di byte in un file e qualunque altra cosa. Chiamiamo P-N un qualunque ingresso di dimensione N e chiamiamo F(P-N) l’algoritmo che opera sull’input P. Inoltre definiamo con K un qualunque P fissato (ad esempio una lista vuota, oppure una lista con 2 elementi, oppure un albero senza sotto-albero destro, etc…

Da questo ricaviamo che un algoritmo ricorsivo è tale se e solo se:

• F(K) ha un risultato immediato (passo base)
• F(P-N) può essere calcolato immediatamente conoscendo il risultato di F(P-M) dove M è minore di N. (passo ricorsivo)

Questo cosa vuol dire. Vuol dire che un algoritmo ricorsivo ricava il risultato su un input di dimensione N grazie al risultato che ottiene su un sotto insieme dell’input iniziale di dimensione M.

Come al solito l’esempio chiarisce molto più di mille parole. Supponiamo di voler scrivere l’algoritmo ricorsivo per invertire una lista ovvero mettere in testa l’ultimo elemento, in seconda posizione il penultimo e così via.

1
2
3
4
5
(define (rovescia lista)

  (cond ((null? lista) '())

      (else (append (rovescia (cdr lista)) (list (car lista))))

  )

)

L’algoritmo non fa altro che appendere l’elemento di testa della lista in coda alla sottolista rovesciata. Ovvero, supponiamo di avere la lista (1 2 3 4) e di volerla rovesciare. Prendendo il primo elemento della lista avremo (1) e la sottolista (2 3 4). Supponiamo di avere la sottolista già rovesciata, ovvero (4 3 2). Ci accorgiamo che per avere la lista originale rovesciata ci basta prendere (1) e metterlo in coda a (4 3 2).

Il problema si riduce quindi a rovesciare (2 3 4). Ma questo a sua volta si riduce a rovesciare (3 4). Che a sua volta si riduce a rovesciare (4). Ma (4) è già rovesciato. E quindi abbiamo concluso.

Ecco un altro esempio:

1
2
3
4
5
6
(define (presente x lista)

   (cond ((null? lista) #f)

      ((= (car lista) x) #t)

      (else (presente x (cdr lista)))

   )

)

Questo algoritmo verifica se l’elemento x è presente nella lista lista. Ancora più semplicemente possiamo applicare il seguente ragionamento ricorsivo:

• Se x è il primo elemento della lista allora l’elemento x è presente. (caso ase)
• Se la lista è vuota allora l’argomento non è presente. (caso base)
• Altrimenti verifico se è presente nel resto della lista. (caso ricorsivo)

Questo è un esempio di ragionamento ricorsivo. In pratica si sposta il problema ad un qualcosa di più piccolo rispetto all’input originale.

Come ultimo esempio vi cito questo:

1
2
3
4
5
(define (sommalista lista)

  (cond ((null? lista) 0)

      (else (+ (car lista) (sommalista (cdr lista))))

  )

)

L’algoritmo non fa altro che sommare tutti gli elementi di una lista. Anche in questo caso il ragionamento ricorsivo è semplice.

• Se la lista è vuota la somma è ZERO. (caso base)
• Altrimenti la somma è uguale al primo elemento più la somma del resto della lista.

Torneremo a parlare di ricorsione ancora e ancora. Cerco di fare il possibile per trattarla in modo comprensibile nonostante gli spazi “ristretti” di un blog.

La prossima lezione affronterà un tema molto importante. Il costo della ricorsione. Cercheremo di trovare un modo semplice per capire quanto costa a livello di prestazioni un algoritmo ricorsivo e come evitare che diventi troppo esoso.