En la lección anterior definimos qué es un algoritmo y escribimos el primero para RutaBus. Ahora daremos un paso atrás para contemplar el panorama completo: los algoritmos se pueden clasificar según varias dimensiones —cómo se estructuran, para qué sirven, si su comportamiento es predecible y si garantizan la solución exacta—. Conocer estas clasificaciones es importante porque te da un mapa mental: cuando te enfrentes a un problema nuevo en RutaBus (o en tu trabajo), sabrás en qué "familia" encaja y qué tipo de herramienta buscar. Además, en esta lección aprenderás en profundidad la recursividad, un concepto transversal que reaparecerá en casi todos los módulos del curso.

1. Las dimensiones de clasificación
2. Por enfoque: iterativos vs recursivos
3. La recursividad en detalle: caso base y caso recursivo
4. Por propósito: búsqueda, ordenación, grafos y más
5. Deterministas vs no deterministas
6. Exactos vs heurísticos/aproximados
7. Avance: estrategias de diseño del Módulo 3

Un mismo algoritmo puede clasificarse a la vez según varios criterios independientes, igual que una parada de RutaBus puede clasificarse a la vez por zona, por accesibilidad y por líneas que la sirven. Las cuatro dimensiones que veremos son:

Por ejemplo, el algoritmo parada_mas_cercana de la lección anterior es iterativo (usa un bucle), de búsqueda (busca un mínimo), determinista (con la misma entrada siempre da la misma salida) y exacto (garantiza encontrar la parada realmente más cercana).

La primera dimensión distingue cómo repite trabajo un algoritmo.

• Un algoritmo iterativo repite pasos mediante bucles (for, while), manteniendo el estado en variables que se van actualizando.
• Un algoritmo recursivo resuelve el problema haciendo que una función se llame a sí misma con una versión más pequeña del problema, hasta llegar a un caso tan simple que se resuelve directamente.

Veamos el mismo problema de RutaBus resuelto con ambos enfoques: contar cuántas paradas tiene una línea, representada como lista de nombres.

La versión recursiva se lee así: "el número de paradas de una lista es 1 (la primera) más el número de paradas del resto de la lista; y una lista vacía tiene 0 paradas". Es una definición del problema en términos de sí mismo, pero con un problema cada vez más pequeño.

Ningún enfoque es "mejor" en abstracto: todo algoritmo recursivo puede reescribirse de forma iterativa y viceversa. La recursión brilla cuando el problema es naturalmente autosimilar (explorar todas las combinaciones de transbordos, recorrer estructuras jerárquicas); la iteración suele ser preferible para recorridos lineales sencillos.

Toda función recursiva bien construida tiene exactamente dos ingredientes:

1. Caso base: la situación tan simple que se resuelve sin recursión. Es la condición de parada. Sin él (o si nunca se alcanza), la función se llamaría a sí misma indefinidamente.
2. Caso recursivo: la función se llama a sí misma con una entrada estrictamente más pequeña o más cercana al caso base, y combina ese resultado parcial con algo de trabajo propio.

Apliquémoslo a un problema real de RutaBus: la línea L2 tiene sus paradas y queremos saber cuántas paradas quedan hasta el final del trayecto desde la parada donde está el usuario.

Sigamos la traza de la ejecución para entender qué ocurre por dentro:

Cada llamada pendiente queda "en espera" en la pila de llamadas hasta que la llamada interior devuelve su resultado. Esto explica el coste en memoria de la recursión: con una línea de 1.000 paradas podría haber hasta 1.000 llamadas apiladas (Python, por defecto, corta en torno a las 1.000 con RecursionError).

Observa también un defecto deliberado del ejemplo: si parada_actual no está en la línea, la lista acabará vacía y linea[0] lanzará IndexError. Un caso base adicional lo arregla:

Regla de oro: enumera primero los casos base (todos), después escribe el caso recursivo, y comprueba que cada llamada recursiva acerca la entrada a algún caso base.

La segunda dimensión clasifica los algoritmos por el tipo de problema que resuelven. Es la clasificación más práctica en el día a día, porque los problemas reales "se parecen" a alguna de estas familias:

Un pequeño ejemplo de cada una de las dos familias más frecuentes, en versión sencilla (las versiones eficientes llegan en el Módulo 4):

En buscar_parada, enumerate nos da a la vez el índice i y el valor parada; devolvemos el índice en cuanto hay coincidencia (no hace falta seguir mirando). En la ordenación usamos el sorted de Python con una función key que indica el criterio (la hora, posición 1 de cada tupla) — en el Módulo 4 abriremos esa "caja negra" y construiremos nuestros propios algoritmos de ordenación.

Un algoritmo es determinista si, ante la misma entrada, ejecuta siempre exactamente los mismos pasos y produce siempre la misma salida. Todos los que hemos escrito hasta ahora lo son, y es la propiedad deseable por defecto: hace el software predecible y fácil de probar.

Un algoritmo no determinista (en la práctica, aleatorizado) incorpora decisiones al azar, por lo que dos ejecuciones con la misma entrada pueden diferir en los pasos intermedios o incluso en la salida. Lejos de ser un defecto, la aleatoriedad es a veces una herramienta valiosa:

Un apunte que retomaremos: algunos algoritmos famosos usan aleatoriedad para mejorar su comportamiento típico — por ejemplo, Quick Sort (Módulo 4) suele elegir su "pivote" al azar. La salida sigue siendo correcta y la misma; lo que varía es el camino.

La última dimensión responde a: ¿el algoritmo garantiza la mejor solución posible?

• Un algoritmo exacto garantiza la solución correcta u óptima. parada_mas_cercana es exacto: la parada devuelta es realmente la más cercana.
• Un algoritmo heurístico o aproximado renuncia a esa garantía a cambio de rapidez o simplicidad: da una solución razonablemente buena casi siempre, pero puede equivocarse o quedarse lejos del óptimo.

¿Por qué renunciar a la exactitud? Porque hay problemas donde encontrar el óptimo exacto es inasumiblemente costoso. Ejemplo clásico adaptado a RutaBus: un supervisor debe visitar 20 paradas en un solo recorrido, minimizando la distancia total (el famoso "problema del viajante"). El número de recorridos posibles es astronómico, así que una heurística razonable es: "desde cada parada, ve siempre a la más cercana no visitada".

Esta heurística produce recorridos buenos en la práctica, pero se puede demostrar que a veces devuelve recorridos claramente peores que el óptimo. Ese es el trato: velocidad a cambio de garantías.

Matiz de vocabulario: se suele llamar aproximado al que ofrece una garantía matemática de cercanía al óptimo (p. ej., "como mucho el doble del óptimo") y heurístico al que no ofrece ninguna, solo buen comportamiento empírico.

Además de las dimensiones anteriores, los algoritmos suelen agruparse por la estrategia de diseño con la que se construyen. Solo las nombramos aquí — cada una tiene su propia lección en el Módulo 3:

• Divide y vencerás (03-01): partir el problema en subproblemas más pequeños, resolverlos y combinar sus soluciones.
• Greedy (voraces) (03-02): construir la solución tomando en cada paso la decisión localmente mejor — la heurística del supervisor que acabamos de ver es de espíritu greedy.
• Programación dinámica (03-03): resolver subproblemas que se repiten guardando sus resultados para no recalcularlos.
• Backtracking (03-04): explorar sistemáticamente todas las opciones, retrocediendo cuando un camino no lleva a solución.

• Olvidar el caso base (o alguno de ellos) en una función recursiva. El síntoma en Python es RecursionError: maximum recursion depth exceeded. Consejo: escribe los casos base antes que el caso recursivo, y pregúntate "¿qué entradas NO deberían provocar otra llamada?".
• Llamada recursiva que no reduce el problema. paradas_restantes(linea, parada_actual) llamándose con la misma lista jamás termina. Verifica que cada llamada recursiva pasa una entrada estrictamente más cercana al caso base.
• Usar recursión para recorridos lineales largos en Python. Con listas de miles de elementos agotarás la pila. Para recorridos simples, prefiere la iteración; reserva la recursión para problemas con estructura ramificada.
• Creer que "no determinista" significa "incorrecto". Un algoritmo aleatorizado bien diseñado es tan legítimo como uno determinista; solo exige disciplina extra en las pruebas (fijar random.seed(42) para reproducirlas).
• Usar una heurística cuando el problema admite solución exacta barata. Antes de aceptar soluciones "aproximadas", comprueba si existe un algoritmo exacto eficiente para tu problema (muchas veces existe y está en el Módulo 4).
• Clasificar el problema demasiado tarde. Consejo profesional: antes de programar, pregunta "¿esto es búsqueda, ordenación, grafos...?". Identificar la familia te lleva directo a soluciones conocidas en lugar de reinventarlas.

Clasifica la función recorrido_supervisor de esta lección según las cuatro dimensiones (enfoque, propósito, determinismo, exactitud) y justifica cada respuesta en una frase.

Escribe una función recursiva hay_parada_recursiva(linea, nombre) que devuelva True si la parada nombre está en la lista linea y False en caso contrario. Identifica explícitamente en comentarios el caso base (o casos base) y el caso recursivo. Después, escribe la versión iterativa y compara: ¿cuál te parece más clara para este problema?

La siguiente función recursiva pretende sumar los minutos de espera de una lista, pero tiene dos errores. Encuéntralos y corrígelos:

Solución 1:

• Enfoque: iterativo — repite mediante un bucle while, sin llamarse a sí misma.
• Propósito: optimización (busca un recorrido corto), apoyándose en operaciones de búsqueda del mínimo.
• Determinismo: determinista — con las mismas paradas y el mismo inicio produce siempre el mismo recorrido (el min de Python resuelve los empates siempre igual: gana el primero).
• Exactitud: heurístico — no garantiza el recorrido de distancia mínima, solo uno razonablemente corto.

Solución 2:

Para un recorrido lineal como este, la versión iterativa suele considerarse más clara y además no consume pila. La recursiva es un buen ejercicio, pero en producción (y en Python) la iterativa es la elección natural. Fíjate en que hacen falta dos casos base: uno de éxito y otro de fracaso.

Solución 3:

Errores:

1. La llamada recursiva no reduce el problema: suma_esperas(esperas) se llama con la misma lista, provocando recursión infinita. Debe ser suma_esperas(esperas[1:]).
2. Falta el caso base de lista vacía: con esperas = [], la condición len(esperas) == 1 es falsa y esperas[0] lanza IndexError. Lo más limpio es que el caso base sea la lista vacía (y así además el caso len == 1 queda cubierto por el caso recursivo).

En esta lección hemos construido un mapa de los tipos de algoritmos según cuatro dimensiones independientes: por enfoque (iterativos frente a recursivos, con la recursividad explicada a fondo mediante caso base y caso recursivo), por propósito (búsqueda, ordenación, grafos, compresión...), por determinismo (predecibles frente a aleatorizados) y por exactitud (exactos frente a heurísticos/aproximados). También hemos avistado las cuatro grandes estrategias de diseño que desarrollaremos en el Módulo 3. Con este mapa ya sabemos qué familias de algoritmos existen; la pregunta natural siguiente es cómo comparar dos algoritmos de la misma familia que resuelven el mismo problema. Para eso necesitamos un lenguaje común e independiente de la máquina: la notación asintótica, protagonista de la próxima lección.