Ripetere con la ricorsione

Niente cicli

Per ripetere un’azione, quasi tutti i linguaggi hanno i cicli: for e while, costruzioni che eseguono lo stesso blocco più volte, aggiornando una variabile a ogni giro (i = i + 1). Ma in Gleam le variabili non si aggiornano mai. E infatti in Gleam i cicli non esistono.

Per ripetere si usa un’idea diversa, più vecchia dei computer stessi: una funzione che chiama se stessa. Si chiama ricorsione.

Il conto alla rovescia

import gleam/int
import gleam/io

pub fn main() -> Nil {
  countdown(3)
}

fn countdown(n: Int) -> Nil {
  case n {
    0 -> io.println("Liftoff!")
    _ -> {
      io.println(int.to_string(n))
      countdown(n - 1)
    }
  }
}

3
2
1
Liftoff!

Segui il programma passo per passo:

1. main chiama countdown(3). 3 non è 0: stampa 3, poi chiama countdown(2).
2. countdown(2): stampa 2, chiama countdown(1).
3. countdown(1): stampa 1, chiama countdown(0).
4. countdown(0): corrisponde alla clausola 0, stampa Liftoff! e non chiama più niente. Fine.

Ogni chiamata fa un pezzettino di lavoro (stampare un numero) e poi affida il resto a un’altra chiamata di se stessa, con un problema un po’ più piccolo (n - 1). Nota anche il tipo: countdown restituisce Nil, perché il suo lavoro è stampare; e in entrambe le clausole l’ultima espressione restituisce Nil (io.println o la chiamata a countdown stessa).

Le due regole

Ogni funzione ricorsiva ha due ingredienti, e sono sempre gli stessi:

• un caso base: una situazione così semplice che la risposta si dà subito, senza chiamarsi di nuovo. Qui è 0 -> io.println("Liftoff!");
• un passo ricorsivo: la funzione fa una parte del lavoro e chiama se stessa con un valore più vicino al caso base. Qui è countdown(n - 1).

Il case è lo strumento perfetto per distinguerli: una clausola per il caso base, una per il passo ricorsivo. Ed è per questo che nel modulo sono arrivati insieme.

Una ricorsione che calcola

Il conto alla rovescia stampa. Ma la ricorsione può anche calcolare un risultato. Quanto fa la somma dei numeri da 1 a n?

import gleam/int
import gleam/io

pub fn main() -> Nil {
  io.println(int.to_string(sum_to(3)))
  io.println(int.to_string(sum_to(100)))
}

fn sum_to(n: Int) -> Int {
  case n {
    0 -> 0
    _ -> n + sum_to(n - 1)
  }
}

6
5050

Il ragionamento è: “la somma fino a 0 è 0; la somma fino a n è n più la somma fino a n - 1”. Se lo srotoli per sum_to(3):

sum_to(3)
= 3 + sum_to(2)
= 3 + (2 + sum_to(1))
= 3 + (2 + (1 + sum_to(0)))
= 3 + (2 + (1 + 0))
= 6

Guarda come si comporta: prima le chiamate scendono fino al caso base, lasciando in sospeso tutte le somme; poi, arrivati a sum_to(0) = 0, i risultati risalgono e le somme in sospeso vengono completate una dopo l’altra.

I fattoriali, e i numeri enormi

Un altro classico è il fattoriale: il fattoriale di 5, scritto 5!, è 5 × 4 × 3 × 2 × 1 = 120. Ha la stessa forma di sum_to, con la moltiplicazione al posto della somma e 1 come caso base (moltiplicare per 1 non cambia niente, come sommare 0).

import gleam/int
import gleam/io

pub fn main() -> Nil {
  io.println(int.to_string(factorial(5)))
  io.println(int.to_string(factorial(30)))
}

fn factorial(n: Int) -> Int {
  case n {
    0 -> 1
    _ -> n * factorial(n - 1)
  }
}

120
265252859812191058636308480000000

Il fattoriale cresce in fretta: 30! ha 33 cifre. In molti linguaggi un numero così non entrerebbe in un intero, ma ricordi i dettagli nerd della lezione 1.4 (“Perché sulla BEAM gli interi non traboccano?”)? Sulla BEAM gli Int crescono quanto serve, e il risultato è esatto fino all’ultima cifra.

Quando la ricorsione non si ferma

E se chiamassimo factorial(-1)? Il caso base è 0, ma partendo da -1 e togliendo 1 a ogni passo si va a -2, -3, -4… e lo zero non arriva mai. Il programma non finisce, e la pila delle chiamate continua a crescere, consumando sempre più memoria.

Il rimedio è rendere il caso base più largo, così che ogni percorso ci arrivi. Con una guardia:

fn factorial(n: Int) -> Int {
  case n {
    n if n <= 1 -> 1
    _ -> n * factorial(n - 1)
  }
}

Ora qualsiasi numero minore o uguale a 1 è un caso base, e da qualsiasi punto di partenza ci si arriva. Per i numeri negativi il fattoriale non ha senso, ma almeno il programma risponde invece di bloccarsi. Ogni volta che scrivi una funzione ricorsiva, fatti la domanda: da qualsiasi valore parta, arriverà sicuramente al caso base?

Contare in avanti

Per contare da un numero a un altro, in avanti, basta passare due argomenti: dove sei e dove devi arrivare. Il caso base è “ho superato l’arrivo”.

import gleam/int
import gleam/io

pub fn main() -> Nil {
  count(from: 1, to: 3)
}

fn count(from n: Int, to last: Int) -> Nil {
  case n > last {
    True -> Nil
    False -> {
      io.println("Step " <> int.to_string(n))
      count(from: n + 1, to: last)
    }
  }
}

Step 1
Step 2
Step 3

Qui il soggetto del case è un Bool, e il caso base non fa niente: restituisce Nil. last resta sempre uguale e viene solo passato avanti, mentre n cresce di uno a ogni chiamata. È il for degli altri linguaggi, scritto con quello che già conosci. (E le etichette from e to rendono la chiamata in main una frase.)

Prima di passare all’esercizio, un indovinello. Cosa succede se in countdown scambi le due righe del passo ricorsivo, e prima chiami countdown(n - 1) e poi stampi?

    _ -> {
      countdown(n - 1)
      io.println(int.to_string(n))
    }

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

import gleam/int
import gleam/io

pub fn main() -> Nil {
  play(from: 1, to: 15)
}

fn play(from n: Int, to last: Int) -> Nil {
  case n > last {
    True -> Nil
    False -> {
      io.println(fizzbuzz(n))
      play(from: n + 1, to: last)
    }
  }
}

fn fizzbuzz(n: Int) -> String {
  case n % 3, n % 5 {
    0, 0 -> "FizzBuzz"
    0, _ -> "Fizz"
    _, 0 -> "Buzz"
    _, _ -> int.to_string(n)
  }
}

Ricapitolando

• In Gleam non ci sono cicli: per ripetere, una funzione chiama se stessa (ricorsione).
• Ogni funzione ricorsiva ha un caso base, che risponde subito, e un passo ricorsivo, che si richiama con un valore più vicino al caso base.
• Il case distingue i due: una clausola per il caso base, una per il passo.
• Le chiamate scendono fino al caso base, poi i risultati risalgono; ogni chiamata in sospeso occupa un posto nello stack.
• Se il caso base non viene mai raggiunto, il programma non finisce: Ctrl+C, poi a e Invio.
• Rendi il caso base abbastanza largo (n if n <= 1) perché ogni percorso ci arrivi.
• Per contare in avanti, passa sia il punto in cui sei sia l’arrivo: count(from: n + 1, to: last).

Nella prossima lezione scopriamo un modo di scrivere la ricorsione che non fa crescere lo stack, e che Gleam trasforma in qualcosa di veloce come un ciclo.