Recursión y Backtracking
Caso base y recursivo, tracing paso a paso, y backtracking (probar-y-retroceder) aplicado a permutaciones y al Sudoku de la I1 (P3 tracing + P4 backtracking, y T0).
cached
Recursión: caso base y caso recursivo
Una función recursiva es una que se llama a sí misma con un problema más pequeño, hasta llegar a un caso que se resuelve directamente. Toda recursión necesita dos partes:
- Caso base: la condición de término que se resuelve sin volver a llamarse (evita la recursión infinita).
- Caso recursivo: reduce el problema y se llama a sí misma acercándose al caso base.
python
def factorial(n): if n <= 1: # CASO BASE return 1 return n * factorial(n - 1) # CASO RECURSIVO print(factorial(4)) # 4 * 3 * 2 * 1 = 24Si falta el caso base (o el caso recursivo no se acerca a él), la función se llama para siempre y Python lanza RecursionError: maximum recursion depth exceeded. Siempre define primero cuándo parar.
Sin caso base → RecursionError
Es contenido que IIC2233 asume de IIC1103 y no vuelve a enseñar, pero lo evalúa aplicado: en la I1 aparece un tracing recursivo (P3) y un backtracking (P4), y en la T0 se usa para encontrar_solucion.
Cargando Quiz...
list_alt
Tracing: seguir la ejecución paso a paso
Hacer tracing es simular a mano la ejecución de una función recursiva, anotando en una tabla cada llamada, sus argumentos y lo que retorna. Es exactamente lo que pide la Pregunta 3 de la I1 (rellenar una tabla paso a paso).
Las llamadas se apilan: cada una espera el resultado de la siguiente, y recién cuando se alcanza el caso base los valores se van devolviendo hacia arriba.
python
def cuenta_regresiva(n): if n == 0: return 'despegue' return cuenta_regresiva(n - 1) # cuenta_regresiva(2)# -> cuenta_regresiva(1)# -> cuenta_regresiva(0)# <- 'despegue' (caso base)# <- 'despegue'# <- 'despegue'alt_route
Backtracking: probar y retroceder
El backtracking explora las combinaciones posibles de una solución probando una opción parcial y retrocediendo (deshaciendo esa elección) apenas se determina que no puede llevar a una solución válida. Se implementa como una recursión con:
- un caso base de éxito (solución completa encontrada),
- un bucle que prueba cada opción, la coloca, y se llama recursivamente,
- si la rama falla, deshace la elección (backtrack) y prueba la siguiente.
python
def permutaciones(elementos, actual=None): actual = actual or [] if not elementos: # CASO BASE: no quedan elementos print(actual) return for i, e in enumerate(elementos): actual.append(e) # elegir restantes = elementos[:i] + elementos[i+1:] permutaciones(restantes, actual) # explorargrid_on
Backtracking en grilla: el Sudoku de la I1
La Pregunta 4 de la I1 pide resolver un Sudoku (matriz 9×9 con cuadrantes 3×3) por backtracking, usando funciones auxiliares ya entregadas: encontrar_celda_vacia, comprobar_fila, comprobar_columna, comprobar_cuadrante. El foco está en la lógica del algoritmo, no en reimplementar esas utilidades.
El patrón esperado:
- Buscar la próxima celda vacía. Si no hay ninguna → caso base: el tablero está completo, retornar
True. - Probar cada valor del 1 al 9 en esa celda.
- Si el valor es válido (fila, columna y cuadrante lo permiten): colocarlo y llamar recursivamente. Si esa llamada resuelve el resto → retornar
True. - Si ningún valor funcionó: deshacer (volver la celda a 0) y retornar
Falsepara que la llamada anterior pruebe otra opción.
python
def resolver(tablero): celda = encontrar_celda_vacia(tablero) if celda is None: # CASO BASE: no hay vacías -> resuelto return True fila, col = celda for valor in range(1, 10): # probar 1..9