Lección 15: Recursión, backtracking e introducción a la programación dinámica
¡Llegaste a la lección final: felicidades! Empecemos con una muñeca matrioska: una muñeca con una más pequeña adentro, hasta llegar a la diminuta que ya no se abre. Eso es exactamente la 'recursión': una función que se llama a sí misma sobre una versión más pequeña del mismo problema, y la muñeca qu
La recursión es como una muñeca rusa: cada muñeca abre una más pequeña, hasta llegar a la diminuta que no se abre (el caso base). El backtracking es probar un camino, y si es un callejón sin salida, cerrarlo e intentar otro. La memoization es anotar en una nota las respuestas que ya calculaste, para no calcularlas de nuevo.
- recursión y backtracking
- Recursión: una función que se llama a sí misma sobre un subproblema más pequeño hasta un caso base. Backtracking: probar una opción, bajar en recursión, y deshacer la opción para explorar todas las posibilidades.
- caso base
- La condición que detiene la recursión y devuelve una respuesta directa sin otra llamada; sin ella la recursión nunca termina.
- memoization
- Guardar en caché resultados de subproblemas (por ejemplo en un dict) para no recalcularlos: evita trabajo repetido y puede acelerar drásticamente la ejecución (por ejemplo, Fibonacci ingenuo de O(2ⁿ) a O(n)).
