Pensamiento recursivo
Casos base y pasos recursivos
Pensamiento recursivo es una lección gratuita de Scala for Backend Engineering & Functional Programming en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Scala for Backend Engineering & Functional Programming, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Scala for Backend Engineering & Functional Programming incluye 4 lecciones en total.
Qué significa la recursión
La recursión ocurre cuando una función se llama a sí misma para resolver una versión más pequeña del mismo problema.
En Scala, la recursión encaja de forma natural con la programación funcional porque permite expresar bucles sin variables mutables.
Toda función recursiva necesita dos cosas: una forma de detenerse y una forma de reducir el problema.
Primero, el caso base
El caso base es la entrada más sencilla que la función puede responder directamente, sin más recursión.
Sin un caso base, la función se llamaría para siempre y fallaría por desbordamiento de pila.
Diseñe siempre el caso base antes del paso recursivo.
def countdown(n: Int): Unit =
if (n < 0) () // base case: stop
else {
println(n)
countdown(n - 1) // recursive step
}Una primera función recursiva
Aquí tiene un programa completo que suma los números del 1 a n.
El caso base devuelve 0; el caso recursivo suma n al resultado de sumar todos los valores inferiores.
def sum(n: Int): Int =
if (n == 0) 0
else n + sum(n - 1)
@main def run(): Unit =
println(sum(5)) // 15Seguir las llamadas
Para entender la recursión, desarrolle las llamadas manualmente.
sum(3) se convierte en 3 + sum(2), que se convierte en 3 + 2 + sum(1), y después en 3 + 2 + 1 + sum(0).
La cadena solo se reduce a un único valor cuando sum(0) devuelve 0: 6.
// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6Recursión sobre listas
Las listas son recursivas por naturaleza: una lista está vacía (Nil) o tiene una cabeza seguida de una cola más pequeña.
Esta estructura se adapta directamente a las funciones recursivas. La lista vacía es el caso base; la cabeza más la recursión sobre la cola forman el paso recursivo.
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}Usar pattern matching con la cola
El patrón :: divide una lista no vacía en su cabeza y su cola.
Cada llamada recursiva trabaja con una lista estrictamente más corta, lo que garantiza el avance hacia Nil.
Esta es la forma canónica de recorrer una lista recursivamente en 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))) // 10Dos llamadas recursivas
Algunos problemas se ramifican en más de una llamada recursiva.
El ejemplo clásico es Fibonacci, donde cada valor depende de los dos anteriores.
Esta versión ingenua es sencilla, pero lenta, porque vuelve a calcular los mismos valores muchas veces.
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
@main def run(): Unit =
println(fib(7)) // 13El coste de la pila
Cada llamada recursiva añade un marco a la pila de llamadas, que debe esperar a que la llamada interna termine.
Con una recursión muy profunda, la pila puede agotarse y lanzar un StackOverflowError.
Contar la profundidad, no solo el tamaño, le ayuda a prever este riesgo.
// This would overflow the stack for large n:
// def deep(n: Int): Int =
// if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000) // StackOverflowErrorReducirse hacia el caso base
El invariante clave de la recursión es que cada llamada debe acercarse al caso base.
Si el argumento no se hace más pequeño o nunca alcanza la condición de parada, la recursión no termina.
Compruébelo antes de ejecutar nada.
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h // t is smaller than xs
}Recursión frente a bucles
El código imperativo utiliza bucles while con contadores mutables; el código funcional utiliza recursión con valores inmutables.
Ambos pueden expresar los mismos cálculos, pero la recursión describe la estructura de los datos de forma más directa.
En Scala, a menudo preferirá la recursión o las funciones de orden superior a los bucles sin más.
// 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)Diseñar una solución recursiva
Un método fiable: identifique el caso base, suponga que la llamada recursiva ya funciona con una entrada más pequeña y, después, combine la cabeza con ese resultado.
Este acto de confianza es el núcleo del pensamiento recursivo. Confía en la llamada para el caso más pequeño y solo se ocupa de un paso.
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))) // 9Comprobación rápida
Compruebe su comprensión de la estructura recursiva.
Recapitulación
La recursión resuelve un problema reduciéndolo a una instancia más pequeña de sí mismo.
Toda función recursiva necesita un caso base que la detenga y un paso recursivo que reduzca la entrada hasta acercarla a ese caso base.
Las listas, con su estructura de Nil y cabeza-cola, son un entorno ideal para desarrollar el pensamiento recursivo. Vigile la profundidad de la pila con entradas muy grandes.
Preguntas frecuentes
¿La lección «Pensamiento recursivo» es gratis?
Sí — el texto completo de «Pensamiento recursivo» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Scala for Backend Engineering & Functional Programming, actualiza a CoddyKit PRO. El curso de Scala for Backend Engineering & Functional Programming incluye 4 lecciones en total.
¿Qué aprenderé en «Pensamiento recursivo»?
Casos base y pasos recursivos Practicas Scala for Backend Engineering & Functional Programming con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Scala for Backend Engineering & Functional Programming?
No se requiere experiencia previa. Scala for Backend Engineering & Functional Programming en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Pensamiento recursivo»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Scala for Backend Engineering & Functional Programming?
Sí. Cada lección de Scala for Backend Engineering & Functional Programming incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Pensamiento recursivo
- Patrones de acumuladores
- foldLeft y foldRight
- reduce y aggregate