La recursión es una técnica de programación en la que una función se llama a sí misma directa o indirectamente para resolver un problema.
Se utiliza cuando un problema puede dividirse en subproblemas más pequeños de la misma naturaleza, resolviendo cada uno de forma similar.
| Archivo | Descripción |
|---|---|
factorial.py |
Cálculo del factorial de un número usando recursión |
fibonacci.py |
Cálculo del n-ésimo número de la serie de Fibonacci |
palindrome.py |
Verificación de si una cadena es un palíndromo usando recursión |
Para que un algoritmo recursivo funcione correctamente debe cumplir con:
- Caso base – Condición que detiene la recursión y devuelve un resultado directo.
- Caso recursivo – Llamada a la misma función con un problema más pequeño o reducido.
- Progreso hacia el caso base – Asegurar que cada llamada reduce el problema.
La recursión es poderosa, pero puede ser ineficiente si no se maneja correctamente, ya que:
- Puede consumir mucha memoria en la pila de llamadas.
- Puede recalcular subproblemas múltiples veces (problema común en Fibonacci sin memoización).
El factorial de un número n (denotado como n!) es el producto de todos los enteros positivos hasta n.
Definición matemática:
n! = n × (n-1)!
0! = 1
Recursivo:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)La secuencia de Fibonacci se define como:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
Recursivo simple:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)Una cadena es un palíndromo si se lee igual de izquierda a derecha que de derecha a izquierda.
Idea recursiva:
- Comparar el primer y último carácter.
- Si son iguales, verificar recursivamente la subcadena central.
- Caso base: cadena vacía o de un solo carácter → es palíndromo.
def is_palindrome(s):
if len(s) <= 1:
return True
if s[0] != s[-1]:
return False
return is_palindrome(s[1:-1])| Algoritmo | Temporal | Espacial | Notas |
|---|---|---|---|
| Factorial | O(n) | O(n) | Una llamada por cada decremento de n |
| Fibonacci | O(2^n) → O(n) | O(n) | Mejorar con memoización/tabulación |
| Palíndromo | O(n) | O(n) | La pila de llamadas crece linealmente |
| Algoritmo | Aplicaciones |
|---|---|
| Factorial | Combinatoria, probabilidad, análisis de algoritmos |
| Fibonacci | Modelado de crecimiento, algoritmos de optimización, estructuras como el Fibonacci Heap |
| Palíndromo | Procesamiento de lenguaje natural, bioinformática (detección de secuencias), criptografía |
- Recursion - GeeksforGeeks – Introducción completa con ejemplos.
- MIT OpenCourseWare - Recursion – Lecciones en video y ejercicios.
- Think Python - Recursion – Capítulo de recursión en un libro gratuito.
- Libro: "Introduction to Algorithms" (CLRS) – Capítulos iniciales sobre recursión y análisis.
- Python Recursion - Real Python – Ejemplos prácticos y buenas prácticas.
Desarrollado con fines educativos ❤️ por @luuiscc_