Lezione laboratorio del 18/12/2023 (ricorsione)

Esercizi

Esercizio 0

Scrivere una funzione ricorsiva somma_numeri(n) che restituisce la somma dei numeri da 0 fino ad n. Si può assumere che n sia positivo.

Esercizio 1

Scrivere una funzione ricorsiva che calcoli la successione di Fibonacci. In particolare, la funzione prende come parametro di input un intero n (che possiamo assumere essere positivo) e restituisce l'n-esimo numero della successione di Fibonacci (F_n). La successione è definita come segue:

• il numero di Fibonacci 0 è 0 (F₀ = 0)
• il numero di Fibonacci 1 è 1 (F₁ = 1)
• gli altri numeri di Fibonacci si ottengono come somma dei due numeri di Fibonacci che lo precedono (F_n = F_n-1 + F_n-2). Così F₂ = F₁ + F₀ = 1 + 0 = 1, F₃ = F₂ + F₁ = 1 + 1 = 2, etc...
  

ATTENZIONE. Sebbene interessate da un punto di vista didattico, scrivere la successione di Fibonacci in modo ricorsivo non è una scelta particolarmente saggia. È molto probabile che il programma che scriverete avrà complessità computazionale esponenziale (O(2ⁿ)).

Esercizio 2

Scrivere una funzione ricorsiva reverse(text) che inverte una stringa. Per esempio, reverse("Hello!") restituisce la stringa "!olleH". Implementare una soluzione ricorsiva che opera come segue:

1. rimuove il primo carattere
2. inverte il resto della stringa
3. combina il carattere rimosso e il risultato della inversione

Esercizio 3

Modificare l'esercizio precedente usando una funzione ricorsiva ausiliaria reverse_sub(text, 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(text, n) deve fare tutto il lavoro, mentre reverse(text) si limita 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 palindroma con il parametro ausiliario).

Esercizio 4

Implementare reverse in maniera iterativa.

Esercizio 5

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

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 le sotto-stringhe della stringa che ottenere rimuovendo il primo carattere.