Ricorsione in coda

Il conto della memoria

Nella lezione precedente abbiamo visto che ogni chiamata ricorsiva in sospeso occupa un posto nello stack. Con sum_to(3) non è un problema. Ma proviamo con numeri più grandi:

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

sum_to(10_000_000) risponde correttamente, 50000005000000. Ma prima di arrivare al caso base accumula dieci milioni di somme in sospeso (“dopo, aggiungi 10000000”, “dopo, aggiungi 9999999”…), e ognuna occupa memoria. Sul computer su cui è stato scritto questo corso, il programma è arrivato a occupare più di 1,5 GB di memoria per sommare dei numeri.

Il colpevole è quel n + ...: dopo che sum_to(n - 1) ha risposto, c’è ancora del lavoro da fare, l’addizione. Per questo la chiamata deve lasciare un promemoria.

Il trucco: portarsi dietro il risultato

E se il lavoro lo facessimo prima di chiamarci, invece che dopo? Basta aggiungere un parametro che si porta dietro il risultato parziale, un accumulatore:

import gleam/int
import gleam/io

pub fn main() -> Nil {
  io.println(int.to_string(sum_loop(3, 0)))
  io.println(int.to_string(sum_loop(10_000_000, 0)))
}

fn sum_loop(n: Int, total: Int) -> Int {
  case n {
    0 -> total
    _ -> sum_loop(n - 1, total + n)
  }
}

6
50000005000000

Srotoliamo sum_loop(3, 0):

sum_loop(3, 0)
= sum_loop(2, 3)
= sum_loop(1, 5)
= sum_loop(0, 6)
= 6

Confrontalo con lo srotolamento di sum_to(3) della lezione precedente: lì le somme si accumulavano in sospeso, sempre più a destra, e si completavano solo alla fine. Qui ogni riga è completa: la somma è già fatta e viaggia nel secondo argomento. Quando si arriva a n = 0, il risultato è già pronto in total, e basta restituirlo.

La chiamata in coda

La differenza chiave è questa: in sum_loop, la chiamata a se stessa è l’ultima cosa che la funzione fa. Non c’è niente da fare dopo, nessuna addizione in sospeso. Una chiamata così si dice in coda (tail call).

E quando una chiamata è in coda, non serve ricordarsi niente: il posto nello stack della chiamata attuale può essere riusato per la successiva. Gleam lo fa automaticamente, e si chiama ottimizzazione delle chiamate in coda. Risultato: sum_loop(10_000_000, 0) ha usato meno di 100 MB, cioè più o meno quello che serve alla BEAM per partire. E sarebbe lo stesso con cento milioni, o un miliardo.

function sum_loop(loop$n, loop$total) {
  while (true) {
    let n = loop$n;
    let total = loop$total;
    if (n === 0) {
      return total;
    } else {
      loop$n = n - 1;
      loop$total = total + n;
    }
  }
}

Riconoscere una chiamata in coda

La domanda da farsi è sempre: dopo che la chiamata ha risposto, resta qualcosa da fare?

Il countdown e il play della lezione precedente, quindi, erano già in coda senza che lo sapessi.

Nascondere l’accumulatore

sum_loop(3, 0) funziona, ma costringe chi la chiama a sapere un dettaglio interno: che il secondo argomento deve partire da 0. Se qualcuno scrivesse sum_loop(3, 1), otterrebbe un risultato sbagliato. La soluzione abituale è una coppia di funzioni:

import gleam/int
import gleam/io

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

/// The sum of the numbers from 1 to n.
pub fn sum_to(n: Int) -> Int {
  sum_to_loop(n, 0)
}

fn sum_to_loop(n: Int, total: Int) -> Int {
  case n {
    0 -> total
    _ -> sum_to_loop(n - 1, total + n)
  }
}

5050

sum_to è la funzione pubblica, con l’interfaccia pulita di prima: un numero dentro, la somma fuori. Il suo unico compito è chiamare sum_to_loop con il valore iniziale giusto dell’accumulatore. sum_to_loop è privata e fa il lavoro vero. Il suffisso _loop è una convenzione diffusa: lo usa anche la libreria standard, dove per esempio string.repeat è implementata con una repeat_loop privata.

Accumulare altro che somme

L’accumulatore può essere di qualsiasi tipo, e l’operazione qualsiasi. Il fattoriale in coda moltiplica, e parte da 1:

pub fn factorial(n: Int) -> Int {
  factorial_loop(n, 1)
}

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

E un accumulatore può anche costruire un risultato cifra per cifra. Questa funzione rovescia le cifre di un numero: a ogni passo stacca l’ultima cifra di n con % 10 e la attacca in fondo all’accumulatore, che si sposta di una posizione con * 10.

import gleam/int
import gleam/io

pub fn main() -> Nil {
  io.println(int.to_string(reverse_digits(1234)))
  io.println(int.to_string(reverse_digits(907)))
}

pub fn reverse_digits(n: Int) -> Int {
  reverse_loop(n, 0)
}

fn reverse_loop(n: Int, acc: Int) -> Int {
  case n {
    0 -> acc
    _ -> reverse_loop(n / 10, acc * 10 + n % 10)
  }
}

4321
709

Srotolato: reverse_loop(1234, 0), poi (123, 4), (12, 43), (1, 432), (0, 4321). L’accumulatore qui fa da “variabile che cambia a ogni giro” dei cicli degli altri linguaggi: la differenza è che non cambia niente, ogni giro ne riceve una nuova.

6 takes 8 steps
7 takes 16 steps
27 takes 111 steps

import gleam/int
import gleam/io

pub fn main() -> Nil {
  io.println(report(6))
  io.println(report(7))
  io.println(report(27))
}

fn report(n: Int) -> String {
  int.to_string(n) <> " takes " <> int.to_string(steps(n)) <> " steps"
}

pub fn steps(n: Int) -> Int {
  steps_loop(n, 0)
}

fn steps_loop(n: Int, count: Int) -> Int {
  case n, n % 2 {
    1, _ -> count
    _, 0 -> steps_loop(n / 2, count + 1)
    _, _ -> steps_loop(3 * n + 1, count + 1)
  }
}

Ricapitolando

• Una ricorsione “normale” lascia del lavoro in sospeso a ogni chiamata, e con molti giri occupa molta memoria.
• Un accumulatore è un parametro che porta avanti il risultato parziale: il lavoro si fa prima di chiamarsi, negli argomenti.
• Una chiamata è in coda quando è l’ultima cosa che la funzione fa. Gleam la ottimizza: lo stack non cresce, qualunque sia il numero di giri.
• La domanda da farsi: dopo la chiamata, resta qualcosa da fare? Se sì, non è in coda.
• Si nasconde l’accumulatore con una funzione pubblica che chiama una privata nome_loop con il valore iniziale.
• Per poche ripetizioni la forma normale va bene; per tante, o per un numero sconosciuto, meglio la coda.

Nella prossima lezione tiriamo le somme del modulo, con una sfida che usa tutto: funzioni, case, guardie e ricorsione.