Esercizi: ricorsione

Esercizi

Esercizio 1

Usando la ricorsione, scrivere una funzione che determini il prodotto degli elementi di una lista.

Suggerimento: prendete ispirazione dalla funzione somma_lista_ricorsiva della lezione sulla ricorsione. Va bene anche la prima versione, quella senza funzione ausiliaria:

Esercizio 2 (P11.8)

Usando la ricorsione, scrivere una funzione che determini il valore massimo di una lista.

Esercizio 3

La funzione 91 di McCarthy è definita come segue:

Scrivere una funzione Python che la implementa. Se corretta, la funzione dovrebbe restituire 91 per tutti gli n ≤ 101.

Suggerimento: guardate la funzione fib_rec della lezione sulla ricorsione.

Esercizio 4 (P11.4)

Si consideri la funzione ricorsiva reverse(s) che restituisce la string s letta da destra a sinistra. Potete trovare il codice nel notebook sulla ricorsione, o copiarlo da qua sotto:

Modificare il codice usando la funzione ricorsiva ausiliaria reverse_sub(s, n) che effettua l'inversione della stringa in input a partire dal carattere in posizione n. Ad esempio, reverse_sub("Hello!", 2) deve restituire "!oll" perché solo i caratteri dalla posizione 2 in poi vengono presi in considerazione. La funzione reverse_sub(s, n) deve fare tutto il lavoro, mentre reverse(s) dovrà limitarsi a richiamare reverse_sub con il parametro n opportuno.

Attenzione: il motivo per utilizzare il parametro aggiuntivo n è per evitare che la funzione reverse_sub debba togliere il primo carattere dalla stringa prima di fare la chiamata ricorsiva. Per tenere traccia del punto in cui siamo arrivati si utilizza il parametro n, mentre la stringa in input viene usata nella chiamata ricorsiva senza nessuna modifica (si pensi alla funzione somma_lista_ricorsiva_aux del notebook sulla ricorsione).

Esercizio 5 (P11.12)

Scrivere una funzione substrings(s) che restituisce una lista di tutte le sottostringhe del parametro s. Ad esempio, le sottostringhe della stringa subsring("rum") deve restituire:

Suggerimento. Prima generate tutte le sotto-stringhe che iniziano con il primo carattere (per questo punto potete anche usare un ciclo for o while). Se la stringa originale è lunga n, di queste sotto-stringhe ce ne sono n. Successivamente generare ricorsivamente le sotto-stringhe della stringa che ottenete rimuovendo il primo carattere.