Recursividad y Backtracking

Recursividad

• Un método recursivo se llama a sí mismo, directa o indirectamente, a través de otro método.
• Todo método recursivo tiene un caso base, que inicia la recursividad.
• La recursión directa: el método se llama a sí mismo.
• La recursión indirecta: un método llama a otro, que llama a otro, etc., hasta volver al método original.
• Se necesita una condición de parada para evitar llamadas recursivas infinitas.

Recursión vs. Iteración

• La iteración usa estructuras repetitivas (bucles).
• La recursión usa la toma de decisiones (llamadas a sí mismo).
• La recursión puede ser menos eficiente en tiempo y memoria, ya que cada llamada crea una nueva copia de las variables.

Backtracking

• Método para probar sistemáticamente todas las posibilidades para encontrar una solución.
• Usa recursividad para explorar posibles soluciones.
• Descompone el problema en tareas parciales y repetitivas.
• Explora todas las posibilidades hasta encontrar la solución (o determinar que no existe).
• Ejemplo: encontrar todos los movimientos de un caballo de ajedrez que visiten todas las casillas del tablero.

Selección Óptima

• Probar todas las posibles configuraciones que cumplen una primera condición.
• Seleccionar la configuración más cercana a una segunda condición (la óptima).
• El tiempo de ejecución puede ser exponencial, por lo que se debe evitar las llamadas recursivas que no mejoren la selección óptima (poda del árbol de decisiones).

Concepto de Pila

• Estructura de datos lineal donde el último elemento en entrar es el primero en salir (LIFO).
• Operaciones:
  • Insertar (push): Agregar un elemento a la cima de la pila.
  • Quitar (pop): Eliminar el elemento de la cima de la pila.
  • CimaPila: Obtener el elemento de la cima sin eliminarlo.
  • PilaVacia: Comprobar si la pila está vacía.
  • PilaLlena: Comprobar si la pila está llena.
  • LimpiarPila: Reiniciar la pila.
• Underflow: Intentar quitar elementos de una pila vacía.
• Overflow: Intentar agregar elementos a una pila llena.

Concepto de Cola

• Estructura de datos lineal donde el primer elemento en entrar es el primero en salir (FIFO).
• Elementos se insertan al final y se eliminan del principio.