1. Funciones Recursivas en Python

1.1. ¿Qué es una Función Recursiva?

Una función recursiva es una función que se llama a sí misma durante su ejecución. Este tipo de función es útil cuando un problema puede dividirse en subproblemas similares al original. La recursividad es una técnica poderosa que se utiliza comúnmente para resolver problemas relacionados con la descomposición de tareas en unidades más pequeñas y repetitivas.

1.2. Estructura de una Función Recursiva

Una función recursiva tiene dos componentes clave:

  1. Caso base: La condición de parada que detiene la recursión.
  2. Llamada recursiva: El proceso en el cual la función se llama a sí misma con argumentos modificados para acercarse al caso base.

1.3. Ejemplo General de Función Recursiva

def funcion_recursiva(parametro):
    if caso_base(parametro):  # Condición de parada
        return resultado_base
    else:
        return funcion_recursiva(parametro_modificado)

1.4. Ejemplo Clásico: Factorial de un Número

El factorial de un número n se define como el producto de todos los números enteros positivos desde 1 hasta n:

  • Factorial de 0 es 1.
  • Factorial de n para n > 0 es n * (n-1) * … * 1.

Usamos recursividad para definir el factorial:

Ejemplo:

def factorial(n):
    if n == 0:  # Caso base: factorial(0) es 1
        return 1
    else:
        return n * factorial(n - 1)  # Llamada recursiva

# Prueba
print(factorial(5))  # Muestra: 120

Explicación:

  1. Si n es 0, la función retorna 1 (caso base).
  2. Para n > 0, la función se llama a sí misma con n-1 hasta que n llega a 0, momento en el cual se resuelve toda la recursión.

Desglose de factorial(5):

  • factorial(5) llama a factorial(4)
  • factorial(4) llama a factorial(3)
  • factorial(3) llama a factorial(2)
  • factorial(2) llama a factorial(1)
  • factorial(1) llama a factorial(0) que devuelve 1
  • La cadena de retornos se va resolviendo:
    • factorial(1) = 1 * 1 = 1,
    • factorial(2) = 2 * 1 = 2,
    • factorial(3) = 3 * 2 = 6,
    • factorial(4) = 4 * 6 = 24,
    • factorial(5) = 5 * 24 = 120.

1.5. Beneficios y Desventajas de la Recursión

Beneficios:

  • Claridad: Para problemas que son naturalmente recursivos, la solución es a menudo más clara y directa con recursión que con bucles.
  • División de problemas: Permite dividir problemas complejos en subproblemas más simples y similares entre sí.

Desventajas:

  • Eficiencia: Las funciones recursivas pueden consumir mucha memoria debido a la pila de llamadas, especialmente si no están bien optimizadas.
  • Límites: En Python, existe un límite en la profundidad de la recursión (por defecto 1000), aunque se puede modificar con sys.setrecursionlimit().

1.6. Recursividad vs Iteración

Cualquier problema que pueda resolverse mediante recursión puede resolverse mediante iteración (bucles). Sin embargo, a veces la recursión ofrece una solución más elegante. La recursividad es preferible cuando:

  • El problema tiene una naturaleza jerárquica o repetitiva.
  • Los subproblemas tienen una relación simple con el problema original.

1.7. Ejemplo Comparativo: Factorial Iterativo vs Recursivo

Factorial con Iteración:

def factorial_iterativo(n):
    resultado = 1
    for i in range(1, n + 1):
        resultado *= i
    return resultado

print(factorial_iterativo(5))  # Muestra: 120

Factorial con Recursión:

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

print(factorial_recursivo(5))  # Muestra: 120

1.8. Problemas Clásicos Resueltos con Recursión

1.8.1. Serie de Fibonacci

La sucesión de Fibonacci es una secuencia en la que cada número es la suma de los dos anteriores. La secuencia empieza con 0 y 1.

Ejemplo

def fibonacci(n):
    if n == 0:  # Caso base
        return 0
    elif n == 1:  # Caso base
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Llamada recursiva

# Prueba
print(fibonacci(6))  # Muestra: 8

1.8.2. Potencias

Calcular la potencia x^n usando recursión:

Ejemplo

def potencia(base, exponente):
    if exponente == 0:  # Caso base
        return 1
    else:
        return base * potencia(base, exponente - 1)  # Llamada recursiva

# Prueba
print(potencia(2, 5))  # Muestra: 32

1.8.3. Búsqueda Binaria

La búsqueda binaria es un algoritmo eficiente para encontrar un elemento en una lista ordenada. Se divide la lista por la mitad y se busca en la mitad correspondiente.

Ejemplo

def busqueda_binaria(lista, objetivo, inicio, fin):
    if inicio > fin:
        return -1  # No encontrado
    medio = (inicio + fin) // 2
    if lista[medio] == objetivo:
        return medio  # Encontrado
    elif lista[medio] > objetivo:
        return busqueda_binaria(lista, objetivo, inicio, medio - 1)
    else:
        return busqueda_binaria(lista, objetivo, medio + 1, fin)

# Prueba
lista = [1, 2, 3, 4, 5, 6, 7, 8, 9]
objetivo = 7
resultado = busqueda_binaria(lista, objetivo, 0, len(lista) - 1)
print(resultado)  # Muestra: 6 (índice de 7 en la lista)

2. Anexos

3. Referencias

4. Enlaces internos

5. Enlaces externos