Funzioni tailrec
Ottimizzi la ricorsione
Funzioni tailrec è una lezione Kotlin Academy gratuita su CoddyKit. Questa è la lezione 3 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 Kotlin Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Kotlin Academy include 4 lezioni in totale.
Che cos'è la ricorsione in coda
Una funzione è ricorsiva in coda quando la chiamata ricorsiva è l'ultima operazione. Kotlin può quindi ottimizzarla trasformandola in un ciclo, evitando lo stack overflow.
tailrec fun countdown(n: Int) {
if (n < 0) return
println(n)
countdown(n - 1)
}
fun main() {
countdown(3)
}Il modificatore tailrec
Aggiunga il modificatore tailrec e il compilatore riscriverà la ricorsione come iterazione, utilizzando uno spazio dello stack costante.
tailrec fun sum(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return sum(n - 1, acc + n)
}
fun main() {
println(sum(100))
}Il modello dell'accumulatore
Per rendere la ricorsione ricorsiva in coda, trasferisca i risultati in un parametro accumulatore, così dopo la chiamata non resta nulla da calcolare.
tailrec fun factorial(n: Int, acc: Long = 1): Long {
if (n <= 1) return acc
return factorial(n - 1, acc * n)
}
fun main() {
println(factorial(10))
}Perché la chiamata deve essere l'ultima
Se accade qualcosa dopo la chiamata ricorsiva (ad esempio si moltiplica il risultato), la chiamata non si trova in posizione di coda e non può essere ottimizzata.
tailrec fun length(s: String, acc: Int = 0): Int {
if (s.isEmpty()) return acc
return length(s.drop(1), acc + 1)
}
fun main() {
println(length("hello"))
}Controesempio di ricorsione non in coda
Questo fattoriale NON è ricorsivo in coda perché la moltiplicazione avviene dopo il ritorno della chiamata. Contrassegnarlo con tailrec genererebbe un avviso.
fun badFactorial(n: Int): Long {
if (n <= 1) return 1
return n * badFactorial(n - 1)
}
fun main() {
println(badFactorial(5))
}Evitare lo stack overflow
Una ricorsione profonda senza tailrec può causare un arresto anomalo. Con tailrec, anche input di grandi dimensioni vengono elaborati utilizzando uno spazio dello stack costante.
tailrec fun count(n: Int, acc: Int = 0): Int {
if (n == 0) return acc
return count(n - 1, acc + 1)
}
fun main() {
println(count(100000))
}Verifica del compilatore
Se contrassegna una funzione con tailrec ma la chiamata non è in posizione di coda, il compilatore emette un avviso e non la ottimizza. Presti attenzione all'avviso.
tailrec fun gcd(a: Int, b: Int): Int {
if (b == 0) return a
return gcd(b, a % b)
}
fun main() {
println(gcd(48, 18))
}Ricorsione in coda e ciclo a confronto
Una funzione tailrec viene compilata in un codice più o meno uguale a quello del ciclo equivalente, ma esprime l'algoritmo in forma ricorsiva.
tailrec fun powerOfTwo(n: Int, acc: Long = 1): Long {
if (n == 0) return acc
return powerOfTwo(n - 1, acc * 2)
}
fun main() {
println(powerOfTwo(10))
}Più parametri
Le funzioni ricorsive in coda spesso trasferiscono diversi parametri di stato, tutti aggiornati nella chiamata ricorsiva.
tailrec fun fib(n: Int, a: Long = 0, b: Long = 1): Long {
if (n == 0) return a
return fib(n - 1, b, a + b)
}
fun main() {
println(fib(20))
}Invertire con tailrec
Un accumulatore può costruire un risultato come una stringa invertita.
tailrec fun reverse(s: String, acc: String = ""): String {
if (s.isEmpty()) return acc
return reverse(s.drop(1), s.first() + acc)
}
fun main() {
println(reverse("kotlin"))
}Una ricerca pratica
Le ricerche iterative si traducono facilmente in ricorsioni in coda.
tailrec fun indexOf(list: List<Int>, target: Int, i: Int = 0): Int {
if (i >= list.size) return -1
if (list[i] == target) return i
return indexOf(list, target, i + 1)
}
fun main() {
println(indexOf(listOf(5, 6, 7), 7))
}Verifica rapida
Verifichi la Sua comprensione delle funzioni tailrec.
Riepilogo
Ha imparato le funzioni tailrec:
tailrectrasforma la ricorsione in posizione di coda in un ciclo, evitando lo stack overflow.- La chiamata ricorsiva deve essere l'ultima operazione.
- Utilizzi un parametro accumulatore per ottenere la forma ricorsiva in coda.
- Il compilatore avvisa quando una funzione non può essere ottimizzata.
tailrec fun sum(n: Int, acc: Int = 0): Int =
if (n == 0) acc else sum(n - 1, acc + n)
fun main() {
println(sum(50))
}Domande Frequenti
La lezione «Funzioni tailrec» è gratuita?
Sì — il testo completo di «Funzioni 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 Kotlin Academy, passa a CoddyKit PRO. Il corso Kotlin Academy include 4 lezioni in totale.
Cosa imparerò in «Funzioni tailrec»?
Ottimizzi la ricorsione Eserciti Kotlin Academy 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 Kotlin Academy?
Non è richiesta alcuna esperienza precedente. Kotlin Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Funzioni 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 Kotlin Academy?
Sì. Ogni lezione Kotlin Academy 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.