¿Qué es la recursividad?
La recursividad es una técnica de programación mediante la cual una función se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños de la misma naturaleza.
Una función recursiva continúa ejecutándose hasta que se alcanza una condición de parada (caso base), momento en el que finalizan las llamadas y comienza el retorno de resultados.
Conceptos fundamentales
Para comprender la recursividad es imprescindible conocer los siguientes conceptos:
- Función recursiva: función que se invoca a sí misma.
- Caso base: condición que detiene la recursión.
- Caso recursivo: parte de la función que realiza la llamada recursiva.
- Pila de llamadas (Call Stack): estructura donde se almacenan las llamadas pendientes.
- Profundidad de recursión: número de llamadas recursivas realizadas.
Funcionamiento de la recursividad
Cuando una función recursiva se ejecuta:
- Comprueba el caso base.
- Si no se cumple, realiza una llamada a sí misma.
- Cada llamada queda almacenada en la pila.
- Al alcanzarse el caso base, las llamadas comienzan a resolverse en orden inverso.
función(4)
↓
función(3)
↓
función(2)
↓
función(1)
↓
Caso base
↑
Retorno
↑
Retorno
↑
Retorno
Estructura de una función recursiva
Toda función recursiva presenta dos partes claramente diferenciadas:
Caso base
Es la condición que detiene las llamadas recursivas.
Sin él, la función nunca finalizaría.
Caso recursivo
Es la parte donde la función vuelve a llamarse con un problema más pequeño.
Cada llamada debe acercarse progresivamente al caso base.
La pila de llamadas (Call Stack)
Cada llamada recursiva crea un nuevo marco de ejecución en la pila de llamadas.
La pila almacena:
- Variables locales.
- Parámetros.
- Dirección de retorno.
Cuando finaliza una llamada, su información se elimina de la pila.
┌──────────────┐
│ función(1) │
├──────────────┤
│ función(2) │
├──────────────┤
│ función(3) │
├──────────────┤
│ función(4) │
└──────────────┘
Ejemplo: cálculo del factorial
El factorial de un número se define como:
n! = n × (n − 1)!
0! = 1
Ejemplo para 4!:
4!
↓
4 × 3!
↓
4 × 3 × 2!
↓
4 × 3 × 2 × 1!
↓
4 × 3 × 2 × 1
=
24
Este problema resulta especialmente adecuado para resolverse mediante recursividad.
Ejemplo: recorrido de un árbol
La recursividad también se utiliza para recorrer estructuras jerárquicas.
Ejemplos:
- Árboles binarios.
- Sistemas de archivos.
- Estructuras XML o JSON.
- Directorios.
Raíz
├── Nodo A
│ ├── A1
│ └── A2
└── Nodo B
├── B1
└── B2
Cada nodo aplica exactamente el mismo algoritmo sobre sus hijos.
Ventajas de la recursividad
Entre sus principales ventajas destacan:
- Código más sencillo.
- Soluciones elegantes.
- Facilita el tratamiento de estructuras jerárquicas.
- Reduce la complejidad de algunos algoritmos.
- Muy utilizada en algoritmos divide y vencerás.
Inconvenientes
La recursividad también presenta limitaciones:
- Mayor consumo de memoria.
- Más llamadas a funciones.
- Menor rendimiento en algunos casos.
- Riesgo de desbordamiento de pila (Stack Overflow).
Recursividad vs Iteración
| Recursividad | Iteración |
|---|---|
| Utiliza llamadas a funciones | Utiliza bucles |
| Emplea la pila de llamadas | No necesita llamadas recursivas |
| Código más elegante | Mayor eficiencia en muchos casos |
| Mayor consumo de memoria | Menor consumo de memoria |
| Adecuada para árboles y grafos | Adecuada para procesos repetitivos simples |
Caso práctico
Situación
Se desea recorrer todos los archivos contenidos en una carpeta y en todas sus subcarpetas.
Solución
La estrategia recursiva consiste en:
- Procesar la carpeta actual.
- Recorrer cada elemento.
- Si un elemento es una subcarpeta, volver a ejecutar el mismo algoritmo sobre ella.
- Finalizar cuando una carpeta no contenga más subcarpetas.
Carpeta
├── Archivo
├── Carpeta A
│ └── Archivo
└── Carpeta B
└── Archivo
Ventajas e inconvenientes
Ventajas
- Código limpio y fácil de mantener.
- Muy útil para problemas jerárquicos.
- Facilita algoritmos divide y vencerás.
- Reduce la complejidad lógica de algunos problemas.
Inconvenientes
- Mayor consumo de memoria.
- Puede ser menos eficiente.
- Riesgo de Stack Overflow.
- Puede resultar difícil de depurar.
Errores habituales
- Olvidar definir el caso base.
- No reducir el problema en cada llamada.
- Confundir recursividad con iteración.
- Pensar que siempre es más eficiente que un bucle.
- Ignorar el consumo de memoria de la pila.
Cómo evitarlos
- Comprobar siempre el caso base.
- Verificar que cada llamada se aproxima al caso base.
- Dibujar el árbol de llamadas para comprender la ejecución.
- Analizar la profundidad máxima de la recursión.
- Comparar la solución recursiva con su equivalente iterativo.
Relaciones con otros temas
La recursividad está estrechamente relacionada con:
- Funciones.
- Pila de llamadas (Call Stack).
- Algoritmos.
- Divide y vencerás.
- Árboles.
- Grafos.
- Búsquedas.
- Ordenación.
- Complejidad algorítmica.
Conceptos clave para recordar
[!NOTE]
- La recursividad consiste en que una función se llama a sí misma.
- Toda función recursiva debe tener un caso base.
- Cada llamada debe acercarse progresivamente al caso base.
- Las llamadas se almacenan en la pila de llamadas (Call Stack).
- Al alcanzarse el caso base, las funciones retornan en orden inverso.
- La recursividad consume más memoria que la iteración.
- Un exceso de llamadas puede producir un Stack Overflow.
- Es especialmente útil para recorrer árboles, directorios, grafos y resolver algoritmos de divide y vencerás.
- Muchos algoritmos recursivos pueden implementarse también mediante iteración.