20 ejercicios de funciones avanzadas en Python (al estilo de Ackermann)

La mayoría de los ejercicios de funciones en Python se centran en ejemplos sencillos: funciones que suman números, calculan promedios o realizan operaciones directas. Sin embargo, cuando avanzamos en la carrera de Informática o en asignaturas de programación teórica, aparecen funciones mucho más exigentes: recursión profunda, crecimiento explosivo, uso intensivo de la pila de llamadas y problemas con un fuerte componente matemático o combinatorio.

En este artículo te propongo 20 ejercicios de funciones avanzadas en Python del estilo de la función de Ackermann: funciones con recursión no trivial, crecimiento muy rápido o lógica compleja. Son ideales para:

• Practicar recursión a fondo.
• Entender problemas que “rompen” los enfoques iterativos simples.
• Acercarte a temas de computabilidad, complejidad y algoritmia.

Aviso práctico: muchos de estos ejercicios pueden alcanzar profundidades de recursión tan grandes que Python lanzará RecursionError. Forma parte del aprendizaje: tendrás que jugar con casos pequeños, optimizar, memoizar o replantear la implementación.

---

Recomendaciones antes de empezar

Antes de ponerte con los ejercicios, ten en cuenta:

1. Sube el límite de recursión solo si sabes lo que haces: import sys sys.setrecursionlimit(10_000) Esto te permitirá probar algunas funciones con recursión más profunda, pero también aumenta el riesgo de agotar la memoria si no tienes cuidado.
2. Empieza siempre con casos muy pequeños (por ejemplo, parámetros menores que 4 o 5).
3. Añade contadores de llamadas o prints de depuración para entender qué está ocurriendo.
4. Cuando sea posible, intenta optimizar con memoización o versiones iterativas.

---

Ejercicio 1 – Implementar la función de Ackermann clásica

La función de Ackermann es un ejemplo clásico de función recursiva que crece mucho más rápido que cualquier función primitiva recursiva. Se define así:

• A(m, n) = n + 1, si m = 0
• A(m, n) = A(m − 1, 1), si m > 0 y n = 0
• A(m, n) = A(m − 1, A(m, n − 1)), si m > 0 y n > 0

Enunciado

Implementa en Python la función ackermann(m, n) que calcule A(m, n) según la definición anterior.

Prueba con valores pequeños, por ejemplo:

• ackermann(0, 0)
• ackermann(2, 3)
• ackermann(3, 4) (si tu máquina aguanta)

Pista de implementación

def ackermann(m: int, n: int) -> int:
    if m == 0:
        return n + 1
    elif m > 0 and n == 0:
        return ackermann(m - 1, 1)
    else:
        return ackermann(m - 1, ackermann(m, n - 1))

---

Ejercicio 2 – Variante acotada de Ackermann

La función de Ackermann crece tan rápido que enseguida rompe cualquier implementación práctica. Una idea es definir una variante acotada donde, si A(m, n) supera cierto límite, devolvemos un valor especial.

Enunciado

Implementa ackermann_acotada(m, n, limite) que:

• Calcule A(m, n) como en el ejercicio anterior.
• Si en algún momento el valor devuelto fuera a superar limite, devuelve directamente limite.

Utiliza esta función para experimentar con los mismos parámetros que en el ejercicio 1, pero con distintos límites.

Pista de implementación

def ackermann_acotada(m: int, n: int, limite: int) -> int:
    valor = ackermann(m, n)
    return valor if valor <= limite else limite

Como mejora, intenta evitar llamar a la Ackermann completa si ya sabes que vas a superar el límite (por ejemplo, propagando un valor especial durante la recursión).

---

Ejercicio 3 – Secuencia de Collatz recursiva

La conjetura de Collatz define la siguiente transformación sobre un número entero positivo n:

• Si n es par, se reemplaza por n / 2.
• Si n es impar, se reemplaza por 3n + 1.

Se repite el proceso hasta llegar a 1.

Enunciado

1. Implementa una función recursiva collatz(n) que devuelva la longitud de la secuencia hasta llegar a 1 (incluyendo el 1).
2. Implementa otra función collatz_lista(n) que devuelva la lista de todos los valores de la secuencia.

Pista de implementación

def collatz(n: int) -> int:
    if n == 1:
        return 1
    if n % 2 == 0:
        return 1 + collatz(n // 2)
    else:
        return 1 + collatz(3 * n + 1)

---

Ejercicio 4 – Collatz con memoización

Calcular continuamente la longitud de la secuencia de Collatz para muchos valores de n es costoso. Podemos almacenar resultados ya calculados.

Enunciado

Implementa collatz_memo(n, memo) donde memo es un diccionario que almacena n -> longitud_de_la_secuencia. Usa esta función para:

• Calcular la longitud de la secuencia de Collatz para todos los n entre 1 y 100_000.
• Determinar qué número menor o igual que 100_000 produce la secuencia más larga.

Pista de implementación

def collatz_memo(n: int, memo: dict[int, int]) -> int:
    if n == 1:
        return 1
    if n in memo:
        return memo[n]
    if n % 2 == 0:
        res = 1 + collatz_memo(n // 2, memo)
    else:
        res = 1 + collatz_memo(3 * n + 1, memo)
    memo[n] = res
    return res

---

Ejercicio 5 – Torres de Hanoi con conteo de movimientos

El problema clásico de las Torres de Hanoi se resuelve de forma recursiva y requiere (2^n – 1) movimientos para n discos.

Enunciado

1. Implementa una función recursiva hanoi(n, origen, destino, auxiliar) que imprima los movimientos necesarios para trasladar n discos desde la torre origen a la torre destino, usando auxiliar como torre auxiliar.
2. Modifica la función para que no imprima, sino que devuelva una lista de movimientos (por ejemplo, tuplas (desde, hasta)).
3. Implementa una función que cuente cuántos movimientos se realizan para n discos y verifica que coincide con la fórmula teórica.

Pista de implementación

def hanoi(n: int, origen: str, destino: str, auxiliar: str, movimientos: list[tuple[str, str]]):
    if n == 1:
        movimientos.append((origen, destino))
    else:
        hanoi(n - 1, origen, auxiliar, destino, movimientos)
        movimientos.append((origen, destino))
        hanoi(n - 1, auxiliar, destino, origen, movimientos)

---

Ejercicio 6 – Función que genera todas las permutaciones

Las permutaciones de una lista con n elementos son todas las formas de ordenarla. Su número crece factorialmente (n!).

Enunciado

Implementa una función recursiva permutaciones(lista) que devuelva una lista con todas las permutaciones posibles de la lista de entrada.

Ejemplo:

permutaciones([1, 2, 3])
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Pista de implementación

• Caso base: permutaciones de una lista vacía o con un solo elemento.
• Caso recursivo: separar un elemento y permutar el resto.

def permutaciones(xs: list) -> list[list]:
    if len(xs) <= 1:
        return [xs[:]]
    res = []
    for i, x in enumerate(xs):
        resto = xs[:i] + xs[i+1:]
        for p in permutaciones(resto):
            res.append([x] + p)
    return res

---

Ejercicio 7 – Generar el conjunto potencia (todas las combinaciones)

El conjunto potencia de un conjunto S es el conjunto de todos sus subconjuntos. Para una lista de n elementos, hay 2^n subconjuntos.

Enunciado

Implementa una función recursiva subconjuntos(lista) que devuelva el conjunto potencia de la lista dada como lista de listas.

Ejemplo:

subconjuntos([1, 2])
# [[], [1], [2], [1, 2]]

Pista

• Caso base: subconjuntos de una lista vacía: [[]].
• Caso recursivo: para cada subconjunto del resto, generamos dos versiones: con y sin el primer elemento.

---

Ejercicio 8 – N-reinas: contar soluciones

El problema de las N reinas consiste en colocar N reinas en un tablero de ajedrez de tamaño N×N de modo que ninguna se ataque.

Enunciado

1. Implementa una función recursiva con backtracking n_reinas(n) que devuelva cuántas soluciones diferentes existen.
2. Opcional: devuelve también una solución representada como lista de columnas, donde el índice es la fila.

Pista

• Representa una solución parcial como una lista cols donde cols[fila] = columna.
• En cada paso, intentas colocar una reina en la siguiente fila.
• Comprueba que no haya conflictos de columna ni diagonales.

---

Ejercicio 9 – Números de Catalan recursivos

Los números de Catalan aparecen en múltiples problemas combinatorios (árboles binarios, formas de parentizar expresiones, etc.). Su definición recursiva es:

[
C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}
]

Enunciado

1. Implementa catalan(n) de forma recursiva directa.
2. Añade memoización para poder calcular valores razonablemente grandes (por ejemplo, hasta n = 20 o 30).

Pista de implementación

def catalan(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n == 0:
        return 1
    total = 0
    for i in range(n):
        total += catalan(i, memo) * catalan(n - 1 - i, memo)
    memo[n] = total
    return total

---

Ejercicio 10 – Cambio de monedas (coin change) recursivo

Queremos saber de cuántas formas diferentes podemos dar cambio para una cantidad usando un conjunto de monedas.

Enunciado

Implementa una función recursiva formas_cambio(cantidad, monedas) que devuelva el número de formas distintas de conseguir cantidad usando las monedas de la lista monedas (puedes usar cada moneda tantas veces como quieras).

Ejemplo:

formas_cambio(5, [1, 2, 5])  # 4 formas

Pista

• Caso base 1: si cantidad == 0, hay exactamente una forma (no usar ninguna moneda).
• Caso base 2: si cantidad < 0 o no quedan monedas, hay 0 formas.
• Caso recursivo: suma de las formas usando al menos una moneda actual + las formas sin usarla.

---

Ejercicio 11 – Función de Hofstadter Q

La secuencia de Hofstadter Q se define así:

• Q(1) = Q(2) = 1
• Para n > 2: Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2))

Enunciado

Implementa hofstadter_q(n) de manera recursiva y:

1. Imprime los primeros 20 valores de la secuencia.
2. Analiza cuántas llamadas recursivas se producen para n grande.

Pista

• Necesitarás memoización para que no explote el número de llamadas.

---

Ejercicio 12 – Secuencias de Hofstadter “male” y “female”

Hofstadter definió dos secuencias entrelazadas F(n) y M(n):

• F(0) = 1, M(0) = 0
• Para n > 0:
  • F(n) = n − M(F(n − 1))
  • M(n) = n − F(M(n − 1))

Enunciado

Implementa dos funciones recursivas F(n) y M(n) que se llamen mutuamente. Imprime los primeros 20 términos de cada una.

Pista

• Usa memoización en dos diccionarios distintos, uno para F y otro para M.

---

Ejercicio 13 – Determinante de una matriz por expansión de cofactores

El determinante de una matriz puede calcularse recursivamente expandiendo por una fila (o columna), lo cual tiene complejidad factorial.

Enunciado

1. Representa matrices como listas de listas de números.
2. Implementa una función determinante(matriz) que:
   • Para matriz 1×1 devuelva su único elemento.
   • Para matriz 2×2 use la fórmula sencilla.
   • Para matrices más grandes, aplique expansión por la primera fila.

Pista

• Necesitas una función auxiliar para obtener el menor de una matriz (eliminando una fila y una columna).

---

Ejercicio 14 – Recorrido de laberinto con backtracking

Representa un laberinto como una matriz de caracteres:

• '#' pared
• ' ' espacio
• 'S' salida

Enunciado

1. Implementa una función recursiva buscar_salida(laberinto, fila, col, visitado) que devuelva True si se puede llegar a 'S' desde la posición (fila, col).
2. Opcional: devuelve el camino seguido como lista de coordenadas.

Pista

• Explora arriba, abajo, izquierda y derecha.
• Evita ciclos controlando las posiciones ya visitadas.

---

Ejercicio 15 – Curva de Koch (definición recursiva)

La curva de Koch es un fractal que se define sustituyendo cada segmento recto por cuatro segmentos más pequeños con forma de pico.

Enunciado

1. Define una función recursiva koch(p1, p2, profundidad) que devuelva la lista de puntos necesarios para dibujar la curva de Koch entre p1 y p2 hasta cierta profundidad.
2. Representa cada punto como una tupla (x, y).

Pista

• Caso base: si profundidad == 0, devuelve simplemente [p1, p2].
• Caso recursivo: divide el segmento en tres partes y reemplaza la parte central por el pico.

---

Ejercicio 16 – Evaluador recursivo de expresiones aritméticas

Queremos evaluar expresiones como cadenas de texto del estilo:

• “3 + 4 * 2”
• “(1 + 2) * (3 + 4)”

Enunciado

1. Diseña una estructura de árbol de expresión (por ejemplo, con nodos que tengan un operador y dos hijos, o un valor numérico).
2. Implementa una función recursiva evalua(arbol) que calcule el valor de la expresión.
3. Opcional: añade un parser sencillo que convierta una cadena en un árbol de expresión.

Pista

• Caso base: un nodo hoja que contiene un número.
• Caso recursivo: evalúa recursivamente los hijos y aplica el operador.

---

Ejercicio 17 – Generación de todas las cadenas binarias sin dos 1 consecutivos

Queremos generar todas las cadenas binarias de longitud n que no contengan “11” como subcadena.

Enunciado

Implementa una función recursiva binarios_sin_dos_unos(n) que devuelva una lista con todas las cadenas (como strings) que cumplan esa condición.

Ejemplo para n = 3:

000, 001, 010, 100, 101

Pista

• Añade dígito a dígito, asegurándote de no colocar un 1 si el anterior ya era 1.
• Este problema es una buena excusa para usar parámetros adicionales en la función recursiva (por ejemplo, último dígito añadido).

---

Ejercicio 18 – Generar todas las combinaciones de paréntesis balanceados

Un clásico de la recursión: dada una n, generar todas las cadenas con n pares de paréntesis bien balanceados.

Enunciado

Implementa parentesis_balanceados(n) que devuelva una lista con todas las cadenas posibles.

Ejemplo para n = 3:

((())), (()()), (())(), ()(()), ()()()

Pista

• Lleva la cuenta de cuántos paréntesis abiertos y cerrados has puesto.
• Solo puedes añadir ')' si hay más abiertos que cerrados.

---

Ejercicio 19 – Problema de la mochila 0/1 (fuerza bruta recursiva)

Tienes una mochila con capacidad limitada y una lista de objetos con peso y valor. Quieres maximizar el valor sin exceder la capacidad.

Enunciado

Implementa una función recursiva mochila(i, capacidad_restante) que devuelva el valor máximo que puedes conseguir considerando los objetos desde el índice i hasta el final.

• Caso base: si i está fuera de rango o capacidad_restante es 0, valor 0.
• Caso recursivo: máximo entre no coger el objeto i y cogerlo (si cabe).

Pista

• Representa los objetos como listas de tuplas (peso, valor).
• Añade memoización con una clave (i, capacidad_restante).

---

Ejercicio 20 – Decorador para limitar profundidad de recursión

Al trabajar con funciones como Ackermann o Hofstadter, es fácil que la recursión se dispare. Un enfoque interesante es escribir un decorador que limite la profundidad.

Enunciado

1. Implementa un decorador limita_profundidad(max_prof) que:
   • Mantenga un contador de profundidad actual.
   • Lance una excepción personalizada si se supera max_prof.
2. Aplícalo a funciones como ackermann, collatz, hofstadter_q, etc., y observa qué profundidad máxima permiten en tu equipo.

Pista de implementación

import functools

class ProfundidadMaximaError(RuntimeError):
    pass

def limita_profundidad(max_prof: int):
    def decorador(func):
        @functools.wraps(func)
        def envoltura(*args, **kwargs):
            if not hasattr(envoltura, "prof"):
                envoltura.prof = 0
            if envoltura.prof >= max_prof:
                raise ProfundidadMaximaError(
                    f"Profundidad máxima {max_prof} superada en {func.__name__}"
                )
            envoltura.prof += 1
            try:
                return func(*args, **kwargs)
            finally:
                envoltura.prof -= 1
        return envoltura
    return decorador

---

Conclusión

Estos 20 ejercicios te permiten ir mucho más allá de las típicas funciones de introducción a Python. Aquí trabajas con:

• Recursión profunda y mutual (funciones que se llaman entre sí).
• Problemas combinatorios con crecimiento explosivo.
• Técnicas de memoización y poda.
• Fractales, backtracking y árboles de búsqueda.

Puedes utilizar este listado como:

• Material de práctica para asignaturas de programación avanzada o computabilidad.
• Base para apuntes de clase o talleres de recursión.
• Banco de ejercicios para exámenes exigentes.

Mi recomendación es que no te limites a copiar el código: modifica los problemas, genera versiones propias y analiza tiempos de ejecución y número de llamadas. Ahí es donde realmente se aprende cómo funciona la recursión en Python a nivel profu