L'annotazione tailrec
Ottimizzazione garantita
L'annotazione tailrec è una lezione Scala for Backend Engineering & Functional Programming gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Scala for Backend Engineering & Functional Programming, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Scala for Backend Engineering & Functional Programming include 4 lezioni in totale.
Che cos'è la ricorsione in coda?
Una chiamata ricorsiva si trova in posizione di coda quando è l'ultima azione eseguita dalla funzione. Una funzione ricorsiva in coda può essere ottimizzata trasformandola in un ciclo che riutilizza un solo stack frame, evitando così l'overflow.
Posizione di coda
In n * factorial(n-1), la chiamata ricorsiva non è l'ultima operazione: la moltiplicazione viene eseguita dopo il suo ritorno. In gcd(b, a % b), invece, la chiamata è l'ultima operazione. Solo quest'ultima funzione è ricorsiva in coda.
L'annotazione @tailrec
Importi scala.annotation.tailrec e annoti un metodo. Il compilatore verifica quindi che la chiamata sia realmente in posizione di coda e applica l'ottimizzazione. In caso contrario, la compilazione fallisce.
import scala.annotation.tailrec
object Main {
@tailrec
def countdown(n: Int): Unit = {
if (n >= 0) {
println(n)
countdown(n - 1)
}
}
def main(args: Array[String]): Unit = countdown(3)
}Ottimizzazione garantita
Il vantaggio principale di @tailrec è la garanzia in fase di compilazione. Viene segnalato immediatamente se la funzione non è sicura rispetto allo stack, invece di scoprirlo tramite un errore a runtime con un input grande.
Un gcd ricorsivo in coda
L'algoritmo di Euclide è già ricorsivo in coda: la chiamata ricorsiva costituisce l'intero risultato del corpo. Annotarla conferma questa proprietà.
import scala.annotation.tailrec
object Main {
@tailrec
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
def main(args: Array[String]): Unit = {
println(gcd(1071, 462))
}
}Cosa interrompe la posizione di coda
Alcuni schemi comuni spostano la chiamata fuori dalla posizione di coda:
- Eseguire calcoli aritmetici sul risultato:
n + f(...). - Racchiudere il risultato in un costruttore:
x :: f(...). - Utilizzare il risultato in un blocco
try.
Esempio non ricorsivo in coda
Questa somma non è ricorsiva in coda perché l'addizione racchiude la chiamata. Annotarla con @tailrec causerebbe un errore di compilazione. (Viene mostrata senza l'annotazione, così può essere eseguita.)
object Main {
def sum(n: Int): Int =
if (n == 0) 0
else n + sum(n - 1)
def main(args: Array[String]): Unit = {
println(sum(100))
}
}Perché non può essere ottimizzata
Poiché n + sum(n - 1) deve ricordare n per completare l'addizione dopo il ritorno della chiamata, ogni livello richiede il proprio stack frame. Il compilatore non può trasformare questa funzione in un ciclo, quindi non è ricorsiva in coda.
Un ciclo ricorsivo in coda su grandi input
Una somma ricorsiva in coda che utilizza un accumulatore può gestire input enormi senza overflow, perché riutilizza un solo frame.
import scala.annotation.tailrec
object Main {
@tailrec
def sumTo(n: Int, acc: Long = 0): Long =
if (n == 0) acc else sumTo(n - 1, acc + n)
def main(args: Array[String]): Unit = {
println(sumTo(1000000))
}
}tailrec richiede final o locale
Per applicare @tailrec, il metodo non deve poter essere sovrascritto: deve essere private, final oppure un metodo locale o annidato. Un metodo aperto potrebbe essere sovrascritto, invalidando l'ottimizzazione, quindi il compilatore lo rifiuta.
Limite della ricorsione reciproca
@tailrec ottimizza solo una funzione che chiama sé stessa. Due funzioni che si chiamano a vicenda (ricorsione reciproca) non possono essere ottimizzate direttamente dalla JVM; a questo scopo serve il trampolining, trattato più avanti.
Verifica rapida
Verifichi la Sua comprensione di @tailrec.
Riepilogo
Ha imparato l'annotazione @tailrec:
- Una chiamata in posizione di coda può essere ottimizzata trasformandola in un ciclo.
@tailrecgarantisce in fase di compilazione la sicurezza rispetto allo stack.- Il metodo deve essere
final,privateo locale. - Si applica solo alla ricorsione su sé stessi, non alla ricorsione reciproca.
Domande Frequenti
La lezione «L'annotazione tailrec» è gratuita?
Sì — il testo completo di «L'annotazione tailrec» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Scala for Backend Engineering & Functional Programming, passa a CoddyKit PRO. Il corso Scala for Backend Engineering & Functional Programming include 4 lezioni in totale.
Cosa imparerò in «L'annotazione tailrec»?
Ottimizzazione garantita Eserciti Scala for Backend Engineering & Functional Programming con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Scala for Backend Engineering & Functional Programming?
Non è richiesta alcuna esperienza precedente. Scala for Backend Engineering & Functional Programming su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «L'annotazione tailrec»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Scala for Backend Engineering & Functional Programming?
Sì. Ogni lezione Scala for Backend Engineering & Functional Programming include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Basi della ricorsione
- L'annotazione tailrec
- Pattern dell'accumulatore
- Trampolining