Basi della ricorsione
Funzioni ricorsive
Basi della ricorsione è una lezione Scala for Backend Engineering & Functional Programming gratuita su CoddyKit. Questa è la lezione 1 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?
La ricorsione si verifica quando una funzione chiama sé stessa per risolvere una versione più piccola dello stesso problema. È particolarmente adatta alla programmazione funzionale, perché sostituisce molti cicli con definizioni autoreferenziali.
Due componenti essenziali
Ogni funzione ricorsiva corretta richiede:
- Un caso base che arresti la ricorsione.
- Un caso ricorsivo che avanzi verso il caso base.
Senza un caso base raggiungibile, la ricorsione continua all'infinito.
Fattoriale
L'esempio classico: n! = n * (n-1)!, con 0! = 1 come caso base.
object Main {
def factorial(n: Int): Int =
if (n <= 1) 1
else n * factorial(n - 1)
def main(args: Array[String]): Unit = {
println(factorial(5))
}
}Tracciare le chiamate
Ogni chiamata ricorsiva si mette in pausa e attende il risultato interno. factorial(3) si espande in 3 * (2 * (1)). Le moltiplicazioni vengono eseguite quando le chiamate terminano.
object Main {
def factorial(n: Int): Int = {
println(s"entering factorial($n)")
if (n <= 1) 1 else n * factorial(n - 1)
}
def main(args: Array[String]): Unit = {
println("result = " + factorial(3))
}
}Somma di una lista
Ricorsione su una lista: la somma è la testa più la somma della coda, mentre la lista vuota ha somma zero.
object Main {
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sum(t)
}
def main(args: Array[String]): Unit = {
println(sum(List(1, 2, 3, 4)))
}
}Lunghezza di una lista
Lo stesso schema calcola la lunghezza: la lista vuota ha lunghezza 0, altrimenti si aggiunge 1 alla lunghezza della coda.
object Main {
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}
def main(args: Array[String]): Unit = {
println(length(List("a", "b", "c")))
}
}Lo stack delle chiamate
Ogni chiamata ricorsiva in attesa utilizza uno stack frame. Una ricorsione profonda accumula molti frame. Per input molto grandi, ciò può esaurire lo stack e generare un StackOverflowError.
Fibonacci
Alcuni problemi si diramano in più chiamate ricorsive. Fibonacci chiama sé stessa due volte: è elegante, ma ha un costo esponenziale.
object Main {
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
def main(args: Array[String]): Unit = {
println(fib(10))
}
}Invertire una lista
La ricorsione può costruire nuove strutture: reverse aggiunge la testa dopo aver invertito la coda.
object Main {
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h
}
def main(args: Array[String]): Unit = {
println(reverse(List(1, 2, 3)))
}
}Ricorsione o iterazione
I cicli modificano un contatore, mentre la ricorsione esprime il problema in modo dichiarativo. Entrambi gli approcci sono validi. La ricorsione è particolarmente adatta ai dati con struttura ad albero e agli algoritmi divide et impera, ma una ricorsione ingenua rischia l'overflow dello stack con input lineari di grandi dimensioni.
Massimo comun divisore
L'algoritmo di Euclide è naturalmente ricorsivo e converge rapidamente.
object Main {
def gcd(a: Int, b: Int): Int =
if (b == 0) a else gcd(b, a % b)
def main(args: Array[String]): Unit = {
println(gcd(48, 18))
}
}Verifica rapida
Verifichi le Sue conoscenze fondamentali sulla ricorsione.
Riepilogo
Ha imparato le basi della ricorsione:
- Ogni funzione ricorsiva richiede un caso base e un caso ricorsivo.
- Ogni chiamata in attesa utilizza uno stack frame; una ricorsione profonda può causare un overflow.
- La ricorsione esprime naturalmente gli algoritmi su liste e alberi.
Ora renderà la ricorsione sicura rispetto allo stack con l'annotazione @tailrec.
Domande Frequenti
La lezione «Basi della ricorsione» è gratuita?
Sì — il testo completo di «Basi della ricorsione» è 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 «Basi della ricorsione»?
Funzioni ricorsive 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 1 di 4.
Quanto tempo richiede la lezione «Basi della ricorsione»?
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