60 ejercicios de funciones recursivas en Python para la carrera de Informática

on noviembre 22, 2025

COMPARTE ESTE ARTÍCULO

En este artículo recopilamos 60 ejercicios clásicos y muy probables de ver en asignaturas de Fundamentos de Programación, Estructuras de Datos o Algoritmia en la carrera de Informática, todos ellos centrados en el uso de funciones recursivas en Python.

La idea es que puedas usar esta lista como:

Material de apoyo para tus clases en Academia San Roque.
Banco de ejercicios para exámenes, prácticas o tareas.
Guía de estudio para estudiantes que quieran dominar la recursión en Python.

En cada ejercicio se incluye:

Enunciado.
Pista o idea de solución.
Posible solución en Python, usando siempre recursión.

1. Factorial de un número

Enunciado
Implementa una función recursiva factorial(n) que calcule el factorial de un número natural n (con n >= 0). Recuerda que:

0! = 1
n! = n * (n-1)! para n > 0

Pista
Identifica el caso base (n == 0) y el caso recursivo (n * factorial(n-1)).

def factorial(n: int) -> int:
    if n < 0:
        raise ValueError("n debe ser >= 0")
    if n == 0:
        return 1
    return n * factorial(n - 1)

2. N-ésimo número de Fibonacci

Enunciado
Implementa una función recursiva fibonacci(n) que devuelva el número de Fibonacci en la posición n, con la convención:

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2) para n >= 2

Pista
Define dos casos base (n == 0 y n == 1) y el caso recursivo.

def fibonacci(n: int) -> int:
    if n < 0:
        raise ValueError("n debe ser >= 0")
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

Nota: Esta implementación es intencionadamente ineficiente, pero muy típica de examen para practicar recursión.

3. Suma de los primeros n enteros

Enunciado
Escribe una función recursiva suma_n(n) que devuelva la suma 1 + 2 + 3 + ... + n.

Pista
Plantea la relación suma_n(n) = n + suma_n(n-1) con caso base en n == 0.

def suma_n(n: int) -> int:
    if n < 0:
        raise ValueError("n debe ser >= 0")
    if n == 0:
        return 0
    return n + suma_n(n - 1)

4. Potencia recursiva

Enunciado
Implementa una función recursiva potencia(base, exponente) que calcule base ** exponente para exponente >= 0.

Pista
Puedes usar la relación a^0 = 1 y a^n = a * a^(n-1).

def potencia(base: float, exponente: int) -> float:
    if exponente < 0:
        raise ValueError("El exponente debe ser >= 0")
    if exponente == 0:
        return 1
    return base * potencia(base, exponente - 1)

5. Producto mediante sumas (sin operador *)

Enunciado
Escribe una función recursiva producto(a, b) que calcule el producto de dos enteros a y b usando solo sumas y restas, sin utilizar el operador *.

Pista
Puedes pensar el producto como sumas repetidas: a * b = a + a * (b-1).

def producto(a: int, b: int) -> int:
    if b < 0:
        return -producto(a, -b)
    if b == 0:
        return 0
    return a + producto(a, b - 1)

6. Suma de elementos de una lista

Enunciado
Implementa una función recursiva suma_lista(lista) que devuelva la suma de los elementos de una lista de enteros.

Pista
Divide la lista en cabeza (lista[0]) y resto (lista[1:]).

def suma_lista(lista: list[int]) -> int:
    if not lista:
        return 0
    return lista[0] + suma_lista(lista[1:])

7. Longitud de una lista (sin usar len)

Enunciado
Escribe una función recursiva longitud(lista) que calcule cuántos elementos tiene una lista sin usar len().

Pista
De nuevo, separa cabeza y cola de la lista.

def longitud(lista: list) -> int:
    if not lista:
        return 0
    return 1 + longitud(lista[1:])

8. Máximo de una lista

Enunciado
Implementa una función recursiva maximo(lista) que devuelva el mayor elemento de una lista de enteros no vacía.

Pista
Compara el primer elemento con el máximo del resto.

def maximo(lista: list[int]) -> int:
    if not lista:
        raise ValueError("La lista no puede estar vacía")
    if len(lista) == 1:
        return lista[0]
    max_resto = maximo(lista[1:])
    return lista[0] if lista[0] > max_resto else max_resto

9. Comprobar si un elemento está en una lista

Enunciado
Escribe una función recursiva contiene(lista, x) que devuelva True si el elemento x está en la lista y False en caso contrario.

Pista
Compara x con la cabeza y, si no está, busca en la cola.

def contiene(lista: list, x) -> bool:
    if not lista:
        return False
    if lista[0] == x:
        return True
    return contiene(lista[1:], x)

10. Invertir una cadena recursivamente

Enunciado
Implementa una función recursiva invertir_cadena(s) que devuelva la cadena s invertida.

Pista
Toma el primer carácter y colócalo al final de la inversión del resto.

def invertir_cadena(s: str) -> str:
    if s == "":
        return ""
    return invertir_cadena(s[1:]) + s[0]

11. Contar ocurrencias de un carácter en una cadena

Enunciado
Escribe una función recursiva contar_caracter(s, c) que cuente cuántas veces aparece el carácter c en la cadena s.

Pista
Divide el problema en el primer carácter y el resto de la cadena.

def contar_caracter(s: str, c: str) -> int:
    if not s:
        return 0
    suma = 1 if s[0] == c else 0
    return suma + contar_caracter(s[1:], c)

12. Búsqueda binaria recursiva

Enunciado
Implementa una función recursiva busqueda_binaria(lista, x, inicio, fin) que busque el elemento x en una lista ordenada de forma ascendente. La función debe devolver el índice de x o -1 si no está.

Pista
Utiliza los índices inicio y fin para delimitar el subarray activo.

def busqueda_binaria(lista: list[int], x: int, inicio: int, fin: int) -> int:
    if inicio > fin:
        return -1

    medio = (inicio + fin) // 2

    if lista[medio] == x:
        return medio
    elif x < lista[medio]:
        return busqueda_binaria(lista, x, inicio, medio - 1)
    else:
        return busqueda_binaria(lista, x, medio + 1, fin)

13. Torres de Hanoi

Enunciado
Escribe una función recursiva hanoi(n, origen, destino, auxiliar) que imprima los pasos necesarios para mover n discos desde la torre origen a la torre destino usando auxiliar como apoyo.

Pista
Caso base: mover 1 disco. Caso recursivo: mover n-1 discos al auxiliar, mover 1 disco al destino y luego los n-1 del auxiliar al destino.

def hanoi(n: int, origen: str, destino: str, auxiliar: str) -> None:
    if n == 1:
        print(f"Mover disco de {origen} a {destino}")
    else:
        hanoi(n - 1, origen, auxiliar, destino)
        print(f"Mover disco de {origen} a {destino}")
        hanoi(n - 1, auxiliar, destino, origen)

14. Conversión de decimal a binario

Enunciado
Implementa una función recursiva decimal_a_binario(n) que reciba un entero no negativo y devuelva una cadena con su representación en binario.

Pista
Utiliza la descomposición por divisiones sucesivas entre 2.

def decimal_a_binario(n: int) -> str:
    if n < 0:
        raise ValueError("n debe ser >= 0")
    if n in (0, 1):
        return str(n)
    return decimal_a_binario(n // 2) + str(n % 2)

15. Comprobar si una cadena es palíndroma

Enunciado
Escribe una función recursiva es_palindromo(s) que determine si una cadena s es un palíndromo (se lee igual de izquierda a derecha que de derecha a izquierda).

Pista
Compara primer y último carácter y haz recursión con la subcadena central.

def es_palindromo(s: str) -> bool:
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return es_palindromo(s[1:-1])

16. Generar todas las permutaciones de una cadena

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

Pista
Toma un carácter y obtén las permutaciones del resto, insertándolo en todas las posiciones posibles.

def permutaciones(s: str) -> list[str]:
    if len(s) <= 1:
        return [s]

    resultado = []
    primera = s[0]
    resto = s[1:]

    for perm in permutaciones(resto):
        for i in range(len(perm) + 1):
            resultado.append(perm[:i] + primera + perm[i:])

    return resultado

17. QuickSort recursivo

Enunciado
Escribe una función recursiva quicksort(lista) que ordene una lista de enteros usando el algoritmo QuickSort.

Pista
Selecciona un pivote, particiona la lista en menores y mayores, y ordena recursivamente.

def quicksort(lista: list[int]) -> list[int]:
    if len(lista) <= 1:
        return lista

    pivote = lista[0]
    menores = [x for x in lista[1:] if x <= pivote]
    mayores = [x for x in lista[1:] if x > pivote]

    return quicksort(menores) + [pivote] + quicksort(mayores)

18. MergeSort recursivo

Enunciado
Implementa una función recursiva mergesort(lista) que ordene una lista de enteros utilizando el algoritmo MergeSort.

Pista
Divide la lista en dos mitades, ordena cada una de forma recursiva y luego fusiónalas.

def mergesort(lista: list[int]) -> list[int]:
    if len(lista) <= 1:
        return lista

    mitad = len(lista) // 2
    izquierda = mergesort(lista[:mitad])
    derecha = mergesort(lista[mitad:])

    return _fusionar(izquierda, derecha)


def _fusionar(izquierda: list[int], derecha: list[int]) -> list[int]:
    if not izquierda:
        return derecha
    if not derecha:
        return izquierda

    if izquierda[0] <= derecha[0]:
        return [izquierda[0]] + _fusionar(izquierda[1:], derecha)
    else:
        return [derecha[0]] + _fusionar(izquierda, derecha[1:])

19. Recorrido recursivo de un árbol binario (preorden)

Enunciado
Supón que tienes un árbol binario representado con una clase Nodo:

class Nodo:
    def __init__(self, valor, izq=None, der=None):
        self.valor = valor
        self.izq = izq
        self.der = der

Implementa una función recursiva preorden(raiz) que imprima los valores del árbol en recorrido preorden (nodo, izquierda, derecha).

Pista
Caso base: nodo None. Caso recursivo: procesar nodo, luego subárbol izquierdo y luego derecho.

def preorden(raiz: Nodo) -> None:
    if raiz is None:
        return
    print(raiz.valor)
    preorden(raiz.izq)
    preorden(raiz.der)

20. Suma de los valores de un árbol binario

Enunciado
Utilizando la misma clase Nodo del ejercicio anterior, implementa una función recursiva suma_arbol(raiz) que devuelva la suma de todos los valores almacenados en el árbol binario.

Pista
La suma de un árbol es el valor de la raíz más la suma de los subárboles izquierdo y derecho.

def suma_arbol(raiz: Nodo) -> int:
    if raiz is None:
        return 0
    return raiz.valor + suma_arbol(raiz.izq) + suma_arbol(raiz.der)

Cómo integrar estos ejercicios en tus clases o en un blog de la Academia

Algunas ideas para sacarles partido en la Academia San Roque o en un WordPress de apoyo a tus asignaturas:

Convertir estos 20 ejercicios en una lista de tareas graduadas (básico → avanzado).
Plantear algunos sin la solución y dejar la resolución para clase o para un vídeo de apoyo.
Usar los ejercicios de ordenación, árboles y búsqueda binaria para enlazar con asignaturas posteriores de Estructuras de Datos.
Proponer variaciones: por ejemplo, modificar fibonacci para memorizar resultados (programación dinámica) o extender permutaciones a listas genéricas.

Con estos ejemplos, el alumnado puede practicar desde la recursión más elemental hasta aplicaciones típicas en algoritmos clásicos que aparecen una y otra vez en la carrera de Informática.

21. Imprimir los números de 1 a n

Enunciado
Implementa una función recursiva imprimir_1_a_n(n) que muestre por pantalla los números del 1 al n en orden creciente.

Pista
Primero imprime hasta n-1 y después muestra n.

def imprimir_1_a_n(n: int) -> None:
    if n <= 0:
        return
    imprimir_1_a_n(n - 1)
    print(n)

22. Imprimir los números de n a 1

Enunciado
Escribe una función recursiva imprimir_n_a_1(n) que muestre por pantalla los números de n hasta 1 en orden decreciente.

Pista
Primero muestra n y luego llamas recursivamente con n-1.

def imprimir_n_a_1(n: int) -> None:
    if n <= 0:
        return
    print(n)
    imprimir_n_a_1(n - 1)

23. Máximo común divisor (MCD) con el algoritmo de Euclides

Enunciado
Implementa una función recursiva mcd(a, b) que devuelva el máximo común divisor de dos enteros a y b usando el algoritmo de Euclides.

Pista
Usa la relación mcd(a, b) = mcd(b, a % b) y el caso base mcd(a, 0) = |a|.

def mcd(a: int, b: int) -> int:
    if b == 0:
        return abs(a)
    return mcd(b, a % b)

24. Suma de los dígitos de un número entero

Enunciado
Escribe una función recursiva suma_digitos(n) que calcule la suma de los dígitos de un entero (positivo o negativo).

Pista
Separa el último dígito (n % 10) y el resto (n // 10).

def suma_digitos(n: int) -> int:
    n = abs(n)
    if n < 10:
        return n
    return n % 10 + suma_digitos(n // 10)

25. Contar el número de dígitos de un entero

Enunciado
Implementa una función recursiva contar_digitos(n) que devuelva cuántos dígitos tiene un entero (sin usar len(str(n))).

Pista
Divide entre 10 recursivamente hasta que el número tenga un solo dígito.

def contar_digitos(n: int) -> int:
    n = abs(n)
    if n < 10:
        return 1
    return 1 + contar_digitos(n // 10)

26. Invertir una lista recursivamente

Enunciado
Escribe una función recursiva invertir_lista(lista) que devuelva una nueva lista con los elementos en orden inverso.

Pista
Similar a invertir una cadena: toma el primer elemento y colócalo al final de la inversión del resto.

def invertir_lista(lista: list) -> list:
    if not lista:
        return []
    return invertir_lista(lista[1:]) + [lista[0]]

27. Comprobar si una lista está ordenada de forma ascendente

Enunciado
Implementa una función recursiva esta_ordenada(lista) que devuelva True si la lista está ordenada de forma ascendente y False en caso contrario.

Pista
Compara elementos consecutivos y reduce el problema a la sublista desde la posición 1.

def esta_ordenada(lista: list[int]) -> bool:
    if len(lista) <= 1:
        return True
    if lista[0] > lista[1]:
        return False
    return esta_ordenada(lista[1:])

28. Contar cuántos números pares hay en una lista

Enunciado
Escribe una función recursiva contar_pares(lista) que devuelva cuántos enteros pares hay en una lista.

Pista
Cuenta 1 si el primer elemento es par y suma lo que salga de la llamada recursiva al resto de la lista.

def contar_pares(lista: list[int]) -> int:
    if not lista:
        return 0
    suma = 1 if lista[0] % 2 == 0 else 0
    return suma + contar_pares(lista[1:])

29. Eliminar todas las apariciones de un elemento en una lista

Enunciado
Implementa una función recursiva eliminar_elemento(lista, x) que devuelva una nueva lista sin ninguna aparición de x.

Pista
Decide si conservar o no el primer elemento y recurre sobre la cola.

def eliminar_elemento(lista: list, x) -> list:
    if not lista:
        return []
    resto = eliminar_elemento(lista[1:], x)
    if lista[0] == x:
        return resto
    else:
        return [lista[0]] + resto

30. Suma de una lista potencialmente anidada

Enunciado
Escribe una función recursiva suma_anidada(lista) que pueda sumar todos los enteros de una lista que puede contener a su vez listas anidadas.

Ejemplo: [1, [2, 3], [4, [5]]] → 15

Pista
Si el elemento actual es una lista, recurre sobre ella; si es un entero, súmalo.

from collections.abc import Iterable


def suma_anidada(lista: list) -> int:
    total = 0
    for elem in lista:
        if isinstance(elem, Iterable) and not isinstance(elem, (str, bytes)):
            total += suma_anidada(list(elem))
        else:
            total += elem
    return total

31. Profundidad máxima de una lista anidada

Enunciado
Implementa una función recursiva profundidad(lista) que calcule la profundidad máxima de una lista anidada.

Ejemplo:

[1, 2, 3] → profundidad 1
[1, [2, 3]] → profundidad 2
[1, [2, [3, 4]]] → profundidad 3

Pista
La profundidad de una lista es 1 más el máximo de la profundidad de sus sublistas.

def profundidad(lista: list) -> int:
    max_prof = 1
    for elem in lista:
        if isinstance(elem, list):
            max_prof = max(max_prof, 1 + profundidad(elem))
    return max_prof

32. Funciones recursivas mutuamente: es_par y es_impar

Enunciado
Define dos funciones recursivas es_par(n) y es_impar(n) tales que:

es_par(0) devuelve True y es_impar(0) devuelve False.
Para n > 0, es_par(n) llama a es_impar(n-1) y es_impar(n) llama a es_par(n-1).

Pista
Es un ejemplo clásico de recursión mutua.

def es_par(n: int) -> bool:
    n = abs(n)
    if n == 0:
        return True
    return es_impar(n - 1)


def es_impar(n: int) -> bool:
    n = abs(n)
    if n == 0:
        return False
    return es_par(n - 1)

33. Potencia rápida (exponenciación por cuadrados)

Enunciado
Implementa una función recursiva potencia_rapida(base, exponente) que calcule base ** exponente usando el método de exponenciación rápida (divide el exponente entre 2 cuando sea posible).

Pista
Si el exponente es par, calcula la potencia de la mitad y multiplícala por sí misma. Si es impar, separa un factor base y reduce el exponente.

def potencia_rapida(base: float, exponente: int) -> float:
    if exponente < 0:
        raise ValueError("El exponente debe ser >= 0")
    if exponente == 0:
        return 1
    if exponente % 2 == 0:
        mitad = potencia_rapida(base, exponente // 2)
        return mitad * mitad
    else:
        return base * potencia_rapida(base, exponente - 1)

34. Conjunto potencia (power set) de una lista

Enunciado
Escribe una función recursiva subconjuntos(lista) que devuelva la lista de todos los subconjuntos posibles de la lista dada.

Ejemplo: [1, 2] → [[], [1], [2], [1, 2]]

Pista
Para cada elemento, los subconjuntos se dividen en los que lo contienen y los que no.

def subconjuntos(lista: list) -> list[list]:
    if not lista:
        return [[]]

    primero = lista[0]
    resto = lista[1:]

    sin_primero = subconjuntos(resto)
    con_primero = [sub + [primero] for sub in sin_primero]

    return sin_primero + con_primero

35. Combinaciones de k elementos de una lista

Enunciado
Implementa una función recursiva combinaciones(lista, k) que devuelva todas las combinaciones posibles de k elementos de la lista.

Pista
Caso base: k == 0 (solo una combinación: la lista vacía) o lista vacía. En el caso recursivo, decide si incluir o no el primer elemento.

def combinaciones(lista: list, k: int) -> list[list]:
    if k == 0:
        return [[]]
    if not lista or k < 0:
        return []

    primero = lista[0]
    resto = lista[1:]

    con_primero = [[primero] + comb for comb in combinaciones(resto, k - 1)]
    sin_primero = combinaciones(resto, k)

    return con_primero + sin_primero

36. Formas de subir una escalera de n peldaños

Enunciado
Una persona puede subir una escalera de n peldaños dando pasos de 1 o 2 peldaños. Implementa una función recursiva formas_escalera(n) que devuelva de cuántas formas distintas se puede subir.

Pista
Caso base: n == 0 (1 forma: no moverse) y n < 0 (0 formas). Caso recursivo: formas_escalera(n) = formas_escalera(n-1) + formas_escalera(n-2).

def formas_escalera(n: int) -> int:
    if n == 0:
        return 1
    if n < 0:
        return 0
    return formas_escalera(n - 1) + formas_escalera(n - 2)

37. Número de caminos en una cuadrícula m x n

Enunciado
En una cuadrícula de m filas y n columnas, empezando en la esquina superior izquierda, puedes moverte solo hacia la derecha o hacia abajo. Implementa una función recursiva caminos(m, n) que devuelva cuántos caminos diferentes hay hasta la esquina inferior derecha.

Pista
Si estás en la última fila o última columna, solo hay 1 camino. En otro caso, caminos(m, n) = caminos(m-1, n) + caminos(m, n-1).

def caminos(m: int, n: int) -> int:
    if m == 1 or n == 1:
        return 1
    return caminos(m - 1, n) + caminos(m, n - 1)

38. Validar paréntesis balanceados en una cadena

Enunciado
Escribe una función recursiva parentesis_balanceados(s) que determine si una cadena formada solo por ( y ) está correctamente balanceada.

Pista
Usa un índice y un contador de apertura. Cada ( suma 1, cada ) resta 1. El contador nunca debe ser negativo y al final debe ser 0.

def _balance(s: str, i: int, abierto: int) -> bool:
    if abierto < 0:
        return False
    if i == len(s):
        return abierto == 0

    if s[i] == '(': 
        return _balance(s, i + 1, abierto + 1)
    else:  # s[i] == ')'
        return _balance(s, i + 1, abierto - 1)


def parentesis_balanceados(s: str) -> bool:
    return _balance(s, 0, 0)

39. Contar el número de hojas en un árbol binario

Enunciado
Usando la clase Nodo definida anteriormente, implementa una función recursiva contar_hojas(raiz) que devuelva cuántos nodos hoja (sin hijos) tiene el árbol binario.

Pista
Un nodo es hoja si sus hijos izquierdo y derecho son None.

def contar_hojas(raiz: Nodo) -> int:
    if raiz is None:
        return 0
    if raiz.izq is None and raiz.der is None:
        return 1
    return contar_hojas(raiz.izq) + contar_hojas(raiz.der)

40. Altura de un árbol binario

Enunciado
Implementa una función recursiva altura(raiz) que calcule la altura de un árbol binario, definida como el número de niveles desde la raíz hasta la hoja más profunda. Un árbol vacío tiene altura 0.

Pista
La altura de un nodo es 1 más el máximo entre la altura de su hijo izquierdo y derecho.

def altura(raiz: Nodo) -> int:
    if raiz is None:
        return 0
    return 1 + max(altura(raiz.izq), altura(raiz.der))

41. Suma de los elementos de una matriz

Enunciado
Implementa una función recursiva suma_matriz(matriz) que calcule la suma de todos los elementos de una matriz representada como lista de listas de enteros.

Pista
Suma la primera fila y luego llama recursivamente con el resto de filas. Puedes reutilizar la función suma_lista del ejercicio 6.

def suma_matriz(matriz: list[list[int]]) -> int:
    if not matriz:
        return 0
    primera_fila = matriz[0]
    resto = matriz[1:]
    return suma_lista(primera_fila) + suma_matriz(resto)

42. Contar cuántos elementos tiene una matriz

Enunciado
Escribe una función recursiva contar_elementos_matriz(matriz) que devuelva cuántos elementos (celdas) tiene una matriz (lista de listas).

Pista
Cuenta los elementos de la primera fila y suma recursivamente los del resto. Puedes reutilizar longitud del ejercicio 7.

def contar_elementos_matriz(matriz: list[list[int]]) -> int:
    if not matriz:
        return 0
    primera_fila = matriz[0]
    resto = matriz[1:]
    return longitud(primera_fila) + contar_elementos_matriz(resto)

43. Buscar un elemento en una matriz

Enunciado
Implementa una función recursiva contiene_matriz(matriz, x) que devuelva True si x está en alguna posición de la matriz y False en caso contrario.

Pista
Busca en la primera fila con contiene (ejercicio 9) y, si no está, recurre sobre el resto de filas.

def contiene_matriz(matriz: list[list[int]], x: int) -> bool:
    if not matriz:
        return False
    if contiene(matriz[0], x):  # reutiliza la función del ejercicio 9
        return True
    return contiene_matriz(matriz[1:], x)

44. Comprobar si una cadena contiene solo dígitos

Enunciado
Escribe una función recursiva solo_digitos(s) que devuelva True si la cadena s está formada únicamente por caracteres numéricos (0-9).

Pista
Comprueba el primer carácter y recurre sobre el resto.

def solo_digitos(s: str) -> bool:
    if s == "":
        return True
    if not s[0].isdigit():
        return False
    return solo_digitos(s[1:])

45. Eliminar vocales de una cadena

Enunciado
Implementa una función recursiva quitar_vocales(s) que devuelva una nueva cadena igual que s pero sin vocales (mayúsculas ni minúsculas).

Pista
Decide si conservar o no el primer carácter y recurre sobre el resto.

def quitar_vocales(s: str) -> str:
    vocales = "aeiouáéíóúüAEIOUÁÉÍÓÚÜ"
    if not s:
        return ""
    primera = s[0]
    resto = quitar_vocales(s[1:])
    if primera in vocales:
        return resto
    return primera + resto

46. Aplanar una lista anidada

Enunciado
Escribe una función recursiva aplanar(lista) que reciba una lista que puede contener a su vez listas anidadas y devuelva una lista plana con todos los elementos.

Ejemplo:
[1, [2, [3, 4]], 5] → [1, 2, 3, 4, 5]

Pista
Si el primer elemento es una lista, aplánala y concaténala con la aplanación del resto.

def aplanar(lista: list) -> list:
    if not lista:
        return []
    cabeza = lista[0]
    cola = lista[1:]
    if isinstance(cabeza, list):
        return aplanar(cabeza) + aplanar(cola)
    else:
        return [cabeza] + aplanar(cola)

47. Subconjuntos que suman a un valor objetivo (Subset Sum)

Enunciado
Implementa una función recursiva subset_sum(lista, objetivo) que devuelva True si existe algún subconjunto de lista cuya suma sea exactamente objetivo.

Pista
Para cada elemento, puedes incluirlo o no incluirlo en la suma.

def subset_sum(lista: list[int], objetivo: int) -> bool:
    if objetivo == 0:
        return True
    if not lista or objetivo < 0:
        return False

    primero = lista[0]
    resto = lista[1:]

    # Caso 1: incluimos el primer elemento
    if subset_sum(resto, objetivo - primero):
        return True
    # Caso 2: no lo incluimos
    return subset_sum(resto, objetivo)

48. Encontrar un camino en un laberinto

Enunciado
Dado un laberinto representado por una matriz de 0s y 1s, donde 0 indica casilla libre y 1 indica muro, implementa una función recursiva encontrar_camino_lab(matriz) que devuelva un camino desde la celda (0, 0) hasta la celda inferior derecha como lista de coordenadas, o None si no existe.

Pista
Usa backtracking: desde cada posición libre, prueba a moverte a sus vecinas (arriba, abajo, izquierda, derecha) evitando ciclos.

def encontrar_camino_lab(matriz: list[list[int]]):
    filas = len(matriz)
    columnas = len(matriz[0]) si filas > 0 else 0

    def backtrack(i: int, j: int, visitados: set[tuple[int, int]]):
        if i < 0 or i >= filas or j < 0 or j >= columnas:
            return None
        if matriz[i][j] == 1 or (i, j) in visitados:
            return None
        if i == filas - 1 and j == columnas - 1:
            return [(i, j)]

        visitados.add((i, j))
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            camino = backtrack(i + di, j + dj, visitados)
            if camino is not None:
                return [(i, j)] + camino
        visitados.remove((i, j))
        return None

    return backtrack(0, 0, set())

(Corrige si por if al pegar en tu código, aquí es solo texto explicativo.)

49. Problema de las N reinas

Enunciado
Implementa una función recursiva n_reinas(n) que devuelva todas las soluciones del problema de las N reinas en un tablero n x n. Cada solución puede representarse como una lista donde la posición i indica la columna de la reina en la fila i.

Pista
Coloca las reinas fila a fila, comprobando que no se ataquen entre sí en columnas ni diagonales.

def n_reinas(n: int) -> list[list[int]]:
    soluciones = []

    def es_valido(solucion_parcial: list[int], fila: int, col: int) -> bool:
        for f_anterior, c_anterior in enumerate(solucion_parcial):
            if c_anterior == col:
                return False
            if abs(f_anterior - fila) == abs(c_anterior - col):
                return False
        return True

    def backtrack(fila: int, solucion_parcial: list[int]):
        if fila == n:
            soluciones.append(solucion_parcial[:])
            return
        for col in range(n):
            if es_valido(solucion_parcial, fila, col):
                solucion_parcial.append(col)
                backtrack(fila + 1, solucion_parcial)
                solucion_parcial.pop()

    backtrack(0, [])
    return soluciones

50. Coeficiente binomial C(n, k)

Enunciado
Escribe una función recursiva binomial(n, k) que calcule el coeficiente binomial $\binom{n}{k}$ (kn), definido por:

$\binom{n}{0} = \binom{n}{n} = 1$ (0n)=(nn)=1
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (kn)=(k−1n−1)+(kn−1)

Pista
Usa directamente la recurrencia anterior como definición.

def binomial(n: int, k: int) -> int:
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    return binomial(n - 1, k - 1) + binomial(n - 1, k)

51. Evaluar un polinomio con el método de Horner

Enunciado
Implementa una función recursiva evaluar_polinomio(coefs, x) que evalúe un polinomio en un punto x usando el método de Horner. Supón que coefs es una lista [a0, a1, ..., an] que representa: $a_0 + a_1 x + a_2 x^2 + \dots + a_n x^n$ a0+a1x+a2x2+⋯+anxn

Pista
Usa la forma anidada de Horner: P(x) = a0 + x(a1 + x(a2 + ...)).

def evaluar_polinomio(coefs: list[float], x: float) -> float:
    if not coefs:
        return 0.0
    if len(coefs) == 1:
        return coefs[0]
    return coefs[0] + x * evaluar_polinomio(coefs[1:], x)

52. Generar todas las cadenas binarias de longitud n

Enunciado
Escribe una función recursiva binarios(n) que devuelva una lista con todas las cadenas binarias de longitud n.

Ejemplo:
n = 2 → ['00', '01', '10', '11']

Pista
Parte de las cadenas de longitud n-1 y añade 0 y 1 al final.

def binarios(n: int) -> list[str]:
    if n == 0:
        return [""]
    menores = binarios(n - 1)
    return [b + "0" for b in menores] + [b + "1" for b in menores]

53. Particiones de un número entero

Enunciado
Implementa una función recursiva particiones(n, maximo=None) que devuelva todas las particiones de un entero positivo n, es decir, todas las formas de escribir n como suma de enteros positivos sin tener en cuenta el orden.

Pista
Limita el tamaño máximo de la siguiente pieza a maximo y decide si usarlo o no.

def particiones(n: int, maximo: int | None = None) -> list[list[int]]:
    if maximo is None or maximo > n:
        maximo = n
    if n == 0:
        return [[]]
    if n < 0 or maximo == 0:
        return []

    # Particiones que usan al menos un 'maximo'
    con_max = [[maximo] + p for p in particiones(n - maximo, maximo)]
    # Particiones que no usan 'maximo'
    sin_max = particiones(n, maximo - 1)

    return con_max + sin_max

54. Recorrido en profundidad (DFS) en un grafo

Enunciado
Dado un grafo representado como un diccionario de listas de adyacencia, implementa una función recursiva dfs(grafo, inicio) que recorra el grafo en profundidad y devuelva el conjunto de nodos visitados.

Pista
Marca el nodo actual como visitado y recurre sobre todos sus vecinos no visitados.

def dfs(grafo: dict, inicio) -> set:
    visitados = set()

    def _dfs(nodo):
        if nodo in visitados:
            return
        visitados.add(nodo)
        for vecino in grafo.get(nodo, []):
            _dfs(vecino)

    _dfs(inicio)
    return visitados

55. Comprobar si un grafo no dirigido es conexo

Enunciado
Usando la función dfs del ejercicio anterior, implementa es_conexo(grafo) que devuelva True si el grafo no dirigido es conexo (es decir, todos los nodos son alcanzables desde cualquiera) y False en caso contrario.

Pista
Elige un nodo cualquiera como inicio, ejecuta dfs y comprueba si has visitado todos los nodos.

def es_conexo(grafo: dict) -> bool:
    if not grafo:
        return True
    inicio = next(iter(grafo))
    visitados = dfs(grafo, inicio)
    return len(visitados) == len(grafo)

56. Búsqueda de una palabra en una sopa de letras

Enunciado
Dada una matriz de caracteres tablero y una palabra palabra, implementa una función recursiva buscar_palabra(tablero, palabra) que devuelva True si la palabra puede formarse moviéndose a celdas vecinas (arriba, abajo, izquierda, derecha) sin reutilizar la misma celda.

Pista
Usa backtracking con un índice sobre la palabra y un conjunto de celdas visitadas.

def buscar_palabra(tablero: list[list[str]], palabra: str) -> bool:
    filas = len(tablero)
    columnas = len(tablero[0]) if filas > 0 else 0

    def backtrack(i: int, j: int, k: int, visitados: set[tuple[int, int]]) -> bool:
        if k == len(palabra):
            return True
        if i < 0 or i >= filas or j < 0 or j >= columnas:
            return False
        if (i, j) in visitados or tablero[i][j] != palabra[k]:
            return False

        visitados.add((i, j))
        for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if backtrack(i + di, j + dj, k + 1, visitados):
                return True
        visitados.remove((i, j))
        return False

    for i in range(filas):
        for j in range(columnas):
            if backtrack(i, j, 0, set()):
                return True
    return False

57. Compresión Run-Length (RLE) recursiva

Enunciado
Implementa una función recursiva rle(s) que reciba una cadena y devuelva una lista de tuplas (caracter, cuenta) con la cantidad de repeticiones consecutivas de cada carácter.

Ejemplo:
"aaabbc" → [('a', 3), ('b', 2), ('c', 1)]

Pista
Cuenta cuántas veces se repite el primer carácter y recurre sobre el resto de la cadena.

def rle(s: str) -> list[tuple[str, int]]:
    if not s:
        return []
    primera = s[0]
    i = 1
    while i < len(s) and s[i] == primera:
        i += 1
    return [(primera, i)] + rle(s[i:])

58. Comprobar si un árbol binario es un árbol de búsqueda (BST)

Enunciado
Usando la clase Nodo de los ejercicios anteriores, implementa una función recursiva es_bst(raiz, minimo, maximo) que determine si el árbol cumple la propiedad de árbol de búsqueda binaria: todos los elementos del subárbol izquierdo son menores que la raíz y todos los del derecho son mayores.

Pista
Propaga un rango válido [minimo, maximo] para cada nodo.

def es_bst(raiz: Nodo, minimo=float("-inf"), maximo=float("inf")) -> bool:
    if raiz is None:
        return True
    if not (minimo < raiz.valor < maximo):
        return False
    return (es_bst(raiz.izq, minimo, raiz.valor) and
            es_bst(raiz.der, raiz.valor, maximo))

59. Contar archivos .py en un directorio y subdirectorios

Enunciado
Implementa una función recursiva contar_py(ruta) que cuente cuántos archivos con extensión .py hay en un directorio y todos sus subdirectorios.

Pista
Usa el módulo os para listar el contenido y llama recursivamente cuando encuentres subdirectorios.

import os


def contar_py(ruta: str) -> int:
    total = 0
    for nombre in os.listdir(ruta):
        camino = os.path.join(ruta, nombre)
        if os.path.isdir(camino):
            total += contar_py(camino)
        elif nombre.endswith(".py"):
            total += 1
    return total

60. Implementar map recursivo sobre una lista

Enunciado
Escribe una función recursiva map_rec(func, lista) que devuelva una nueva lista resultante de aplicar la función func a cada elemento de lista.

Pista
Aplica func al primer elemento y concatena con la llamada recursiva al resto de la lista.

def map_rec(func, lista: list) -> list:
    if not lista:
        return []
    return [func(lista[0])] + map_rec(func, lista[1:])

Contenido restringido

Categories:

Informática

Tags:

Sin etiqueta

Comments are closed