Recursividad

Una función recursiva resuelve un problema reduciéndolo a uno igual pero más pequeño y llamándose a sí misma con él. El factorial de 5 es 5 por el factorial de 4, que es 4 por el de 3… hasta llegar al caso base, que se resuelve directamente.

Sin caso base, la función se llamaría sin fin hasta agotar la memoria reservada para las llamadas (un «desbordamiento de pila»). Es muy útil para recorrer estructuras en árbol, como carpetas dentro de carpetas.

Un ejemplo

factorial(n) devuelve 1 si n es 1 o menos (caso base) y, si no, n * factorial(n - 1).

Por qué importa

Una función recursiva se llama a sí misma para resolver un problema dividiéndolo en versiones más pequeñas del mismo problema. Es la forma natural de tratar estructuras que contienen otras iguales a ellas: carpetas dentro de carpetas, árboles, expresiones anidadas o un documento JSON con niveles. También es la base de algoritmos clásicos como la búsqueda binaria, la ordenación rápida o el recorrido de grafos.

Toda función recursiva correcta necesita dos partes: un caso base, que se resuelve directamente y detiene la recursión, y un caso recursivo, que se acerca al caso base en cada llamada. Por ejemplo, el factorial de n es n por el factorial de n - 1, y el de 0 vale 1. Cualquier recursión puede reescribirse con un bucle, pero en problemas con estructura de árbol el código recursivo suele ser mucho más corto y claro.

Confusiones frecuentes

El error típico es olvidar el caso base o no acercarse a él, lo que provoca recursión infinita: cada llamada ocupa espacio en la pila y acaba con un desbordamiento de pila (stack overflow, o RecursionError en Python, que limita la profundidad por defecto). También se asume que recursión es siempre mejor o siempre peor que un bucle: la recursiva puede ser más elegante, pero consume memoria por cada llamada y, aplicada sin cuidado, repite cálculos, como en el cálculo ingenuo de Fibonacci. Algunos lenguajes optimizan la recursión de cola; otros, como Python, no.

Preguntas frecuentes

¿Qué es un desbordamiento de pila?

Un error que ocurre cuando hay demasiadas llamadas anidadas pendientes y se agota la memoria reservada para ellas. Con recursión suele indicar que falta el caso base o que nunca se alcanza.

¿Cuándo conviene usar recursión en lugar de un bucle?

Cuando el problema es naturalmente recursivo, como recorrer un árbol o carpetas anidadas. Si basta con repetir un número de veces, un bucle es más simple y eficiente.