Pensare in modo ricorsivo
Casi base e passaggi ricorsivi.
Pensare in modo ricorsivo è 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 cosa significa la ricorsione
La ricorsione si verifica quando una funzione chiama sé stessa per risolvere una versione più piccola dello stesso problema.
In Scala, la ricorsione si adatta naturalmente alla programmazione funzionale, perché consente di esprimere i cicli senza variabili mutabili.
Ogni funzione ricorsiva richiede due elementi: un modo per fermarsi e un modo per ridurre il problema.
Prima il caso base
Il caso base è l'input più semplice a cui la funzione può rispondere direttamente, senza ulteriore ricorsione.
Senza un caso base, la funzione chiamerebbe sé stessa all'infinito e andrebbe in errore per overflow dello stack.
Progetti sempre il caso base prima del passo ricorsivo.
def countdown(n: Int): Unit =
if (n < 0) () // base case: stop
else {
println(n)
countdown(n - 1) // recursive step
}Una prima funzione ricorsiva
Ecco un programma completo che somma i numeri da 1 a n.
Il caso base restituisce 0; il caso ricorsivo aggiunge n alla somma di tutti i valori precedenti.
def sum(n: Int): Int =
if (n == 0) 0
else n + sum(n - 1)
@main def run(): Unit =
println(sum(5)) // 15Tracciare le chiamate
Per comprendere la ricorsione, espanda manualmente le chiamate.
sum(3) diventa 3 + sum(2), che diventa 3 + 2 + sum(1), poi 3 + 2 + 1 + sum(0).
Solo quando sum(0) restituisce 0 la catena si ricompone in un unico valore: 6.
// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6Ricorsione sulle liste
Le liste sono ricorsive per natura: una lista è vuota (Nil) oppure è composta da una testa seguita da una coda più piccola.
Questa struttura si adatta direttamente alle funzioni ricorsive. La lista vuota è il caso base; la testa più la ricorsione sulla coda costituiscono il passo ricorsivo.
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}Corrispondenza dei pattern sulla coda
Il pattern :: divide una lista non vuota nella testa e nella coda.
Ogni chiamata ricorsiva opera su una lista strettamente più corta, garantendo l'avvicinamento a Nil.
Questo è il modo canonico di scorrere ricorsivamente una lista in Scala.
def sumList(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sumList(t)
}
@main def run(): Unit =
println(sumList(List(1, 2, 3, 4))) // 10Due chiamate ricorsive
Alcuni problemi si diramano in più di una chiamata ricorsiva.
L'esempio classico è Fibonacci, in cui ogni valore dipende dai due valori precedenti.
Questa versione ingenua è semplice ma lenta, perché ricalcola gli stessi valori molte volte.
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
@main def run(): Unit =
println(fib(7)) // 13Il costo dello stack
Ogni chiamata ricorsiva aggiunge un frame allo stack delle chiamate, che deve attendere la restituzione della chiamata interna.
Con una ricorsione molto profonda, lo stack può esaurirsi e generare uno StackOverflowError.
Contare la profondità, non solo la dimensione, aiuta a prevedere questo rischio.
// This would overflow the stack for large n:
// def deep(n: Int): Int =
// if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000) // StackOverflowErrorRidursi verso il caso base
L'invariante fondamentale della ricorsione è che ogni chiamata deve avvicinarsi al caso base.
Se l'argomento non diminuisce o non raggiunge mai la condizione di arresto, la ricorsione non termina.
Verifichi questo aspetto prima di eseguire qualsiasi operazione.
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h // t is smaller than xs
}Ricorsione e cicli
Il codice imperativo usa cicli while con contatori mutabili; il codice funzionale usa la ricorsione con valori immutabili.
Entrambi possono esprimere gli stessi calcoli, ma la ricorsione descrive più direttamente la struttura dei dati.
In Scala, spesso preferirà la ricorsione o le funzioni di ordine superiore ai cicli elementari.
// Imperative
var total = 0
for (i <- 1 to 5) total += i
// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)Progettare una soluzione ricorsiva
Una procedura affidabile consiste nell'identificare il caso base, supporre che la chiamata ricorsiva funzioni già sull'input più piccolo e poi combinare la testa con il risultato.
Questo atto di fiducia è il cuore del pensiero ricorsivo. Si affida alla chiamata più piccola e gestisce un solo passaggio.
def maxOf(xs: List[Int]): Int = xs match {
case h :: Nil => h
case h :: t => math.max(h, maxOf(t))
}
@main def run(): Unit =
println(maxOf(List(3, 9, 2, 7))) // 9Verifica rapida
Verifichi la sua comprensione della struttura ricorsiva.
Riepilogo
La ricorsione risolve un problema riducendolo a un'istanza più piccola di sé stesso.
Ogni funzione ricorsiva richiede un caso base per fermarsi e un passo ricorsivo che riduca l'input verso quel caso base.
Le liste, con la loro struttura Nil e testa-coda, sono un ambiente ideale per esercitarsi con il pensiero ricorsivo. Presti attenzione alla profondità dello stack con input molto grandi.
Domande Frequenti
La lezione «Pensare in modo ricorsivo» è gratuita?
Sì — il testo completo di «Pensare in modo ricorsivo» è 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 «Pensare in modo ricorsivo»?
Casi base e passaggi ricorsivi. 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 «Pensare in modo ricorsivo»?
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
- Pensare in modo ricorsivo
- Pattern dell'accumulatore
- foldLeft e foldRight
- reduce e aggregate