Recursión — Python: Funciones

• ¿Por qué usar recursión?
• Tipos de recursión
• Resumen

La recursión en programación es cuando una función se llama a sí misma. Este concepto proviene de la matemática, donde muchas funciones se definen recursivamente.

⏬ Ejemplo básico:

def f():
    f()

Este código se ejecutará infinitamente, ya que la función nunca tiene un punto de terminación.

Para comprender mejor la recursión, imaginemos un problema cotidiano:

📖 Ordenar libros en una estantería

• Con 3 libros hay 6 combinaciones posibles.
• Con 4 libros hay 24 combinaciones.
• Con 13 libros hay casi tantas como personas en el planeta.
• Con 25 libros hay más combinaciones que átomos en el cuerpo humano.

El número de combinaciones posibles se calcula con el factorial n!, que se define como:

El número de combinaciones posibles se calcula con el factorial n!, por ejemplo, 3! = 3 × 2 × 1 = 6.

Podemos escribir una función factorial en Python:

def factorial(n):
  return 1 * 2 * 3 * 4  # ❌ No sabemos el valor de `n` de antemano

Para resolver esto, podemos definir factorial recursivamente:

• Si n == 0, el resultado es 1.
• Si n > 0, el resultado es n × (n - 1)!.

Implementación en Python:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

answer = factorial(3)

¿Cómo funciona este código?

Cuando ejecutamos factorial(3), se crean múltiples llamadas recursivas:

factorial(3)   →   3 * factorial(2)
factorial(2)   →   2 * factorial(1)
factorial(1)   →   1 * factorial(0)
factorial(0)   →   1  (Caso base)

El cálculo se resuelve de abajo hacia arriba:

3 * 2 * 1 * 1  →  3 * 2 * 1  →  3 * 2  →  6

Reglas clave de la recursión:

📌 Caso base: Define cuándo detener la recursión (en este caso, n == 0).

📌 Regla de recursión: Indica cómo reducir el problema (n * factorial(n - 1)).

¿Por qué usar recursión?

Algunos algoritmos son más fáciles de escribir recursivamente, especialmente cuando trabajan con estructuras de datos recursivas como árboles o HTML anidado.

Ejemplo: Un navegador web procesa HTML recursivamente porque las etiquetas pueden contener otras etiquetas. Sin embargo, la recursión usa memoria adicional para cada llamada, por lo que debe manejarse con cuidado.

Tipos de recursión

Según la forma en que se llama

Según el número de llamadas recursivas

Veamos ejemplos de cada tipo.

⏬ Ejemplo de recursión lineal

La Conjetura de Collatz es un ejemplo clásico de recursión lineal, donde cada llamada a la función genera solo una nueva llamada recursiva.

def collatz(n):
    if n == 1:
        return True
    if n % 2 == 0:
        return collatz(n // 2)
    return collatz(n * 3 + 1)

Características:

• En cada ejecución, la función realiza una única llamada recursiva.
• Su flujo puede representarse como una cadena de llamadas sucesivas, lo que facilita su seguimiento.

Otro caso de recursión lineal es el recorrido de una lista:

# Función que suma todos los elementos de una lista usando recursión
def sum(array):
    head, *tail = array
    if not tail:
        return head
    return head + sum(tail)

Aquí descomponemos la lista en cabeza (primer elemento) y cola (resto de la lista) hasta que la cola esté vacía.

⏬ Ejemplo visual:

[1, 2, 3] →
[1, [2, 3]] →
[1, [2, [3]]] →
[1, [2, [3, []]]]

Cada paso reduce el problema hasta llegar a un caso base.

⏬ Ejemplo de recursión cascada

def fibonacci(n):
    if n <= 2:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Características:

• Cada llamada recursiva genera dos nuevas llamadas.
• La cantidad de llamadas crece exponencialmente, lo que puede afectar el rendimiento.

⏬ Ejemplo visual para fibonacci(5):

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2) = 1
│   │   ├── fibonacci(1) = 1
│   ├── fibonacci(2) = 1
├── fibonacci(3)
│   ├── fibonacci(2) = 1
│   ├── fibonacci(1) = 1

❌ Problema: El mismo valor se calcula varias veces, por lo que este enfoque puede ser ineficiente.

✅ Solución: Podemos mejorar esto usando memorización o programación dinámica.

Resumen

• La recursión es una herramienta poderosa que nos permite definir funciones que se llaman a sí mismas.
• Tiene un caso base que define el punto de detención.
• Existen diferentes tipos de recursión, siendo las más comunes:
  • Lineal: Se llama a sí misma solo una vez.
  • Cascada: Se llama varias veces, lo que puede generar crecimiento exponencial de llamadas.
• No siempre es la mejor opción, ya que usa más memoria que los ciclos iterativos.

En estructuras como árboles y grafos, la recursión puede simplificar enormemente el código.