Recursividad y optimización de algoritmos

Qué es un algoritmo recursivo

Un algoritmo es recursivo cuando, para resolver un problema, se llama a sí mismo con una versión más pequeña del mismo problema. Es como las muñecas rusas: abrís una y adentro hay otra igual, pero más chica, hasta llegar a la más pequeña, que ya no se abre.

Esa muñeca final es la clave: sin ella, el proceso no terminaría nunca. Por eso toda función recursiva necesita dos partes.

El factorial es el ejemplo clásico. $n!$ es el producto de todos los naturales de 1 a $n$, y se define así:

• Caso base: $0! = 1$

• Caso recursivo: $n! = n \cdot (n-1)!$ para $n \geq 1$

Trazar una función recursiva

Trazar es seguir a mano cada llamada y anotar qué devuelve. Se usa pseudocódigo en español: función, si … sino y devolver.

función suma(n):

    si n = 1:

        devolver 1

    sino:

        devolver n + suma(n - 1)

Fijate en los resultados: 1, 3, 6, 10. La función calcula $1 + 2 + 3 + \dots + n$, la suma de los primeros $n$ números naturales. Por qué: cada llamada suma su propio $n$ al total de los anteriores.

Una definición recursiva también sirve para sucesiones. Por ejemplo, 2, 4, 8, 16, 32… cada término es el doble del anterior:

• Caso base: $T(1) = 2$

• Caso recursivo: $T(n) = 2 \cdot T(n-1)$ para $n \geq 2$

función suma(n):

    si n = 1:

        devolver 1

    sino:

        devolver n + suma(n - 1)

Dividir y vencer

Dividir y vencer es una estrategia: partís un problema grande en subproblemas más pequeños del mismo tipo, resolvés cada uno y combinás las respuestas. Se lleva muy bien con la recursividad, porque cada parte se resuelve con la misma idea.

Volvamos a las 200 fichas: se reparten en montones de, por ejemplo, 50; se ordena cada montón (más fácil, pues es chico) y luego se juntan los montones ya ordenados. Cada paso trabaja con menos fichas, y juntar montones ordenados es rápido.

Eficiencia: contar pasos

Dos algoritmos pueden resolver lo mismo y ser muy distintos. La eficiencia se mide contando cuántos pasos (por ejemplo, comparaciones) necesita el algoritmo, sobre todo cuando los datos son muchos. No se mide en segundos, porque eso depende de la computadora.

Caso: buscar la matrícula 4,350 en una lista de 1,000 estudiantes ordenada de menor a mayor.

• Búsqueda uno por uno (A): en el peor caso revisa los 1,000 elementos.

• Búsqueda por mitades (B): compara con el elemento del medio y descarta la mitad que no sirve. Es dividir y vencer.

Con B, la lista se reduce así: 1,000 → 500 → 250 → 125 → … → 1. Cada comparación la parte a la mitad. Como $2^{10} = 1{,}024 > 1{,}000$, bastan unas 10 comparaciones como máximo.

Recursividad ineficiente y su mejora

Que un algoritmo sea recursivo no garantiza que sea eficiente. El caso típico es Fibonacci:

• $F(1) = 1$, $F(2) = 1$

• $F(n) = F(n-1) + F(n-2)$ para $n \geq 3$

Cada llamada genera dos llamadas nuevas. Mirá el árbol para $F(5)$:

Observá que $F(3)$ se calcula dos veces y $F(2)$ tres veces. Con $F(6)$ el desperdicio crece: $F(3)$ se calcula 3 veces. Al aumentar $n$, el árbol casi se duplica en cada nivel, y el trabajo explota.

Dos mejoras:

• Guardar resultados ya calculados (una tabla o lista) y consultarlos antes de recalcular.

• Usar un ciclo que avance desde $F(1)$ y $F(2)$ guardando solo los dos últimos valores.

Así cada $F(k)$ se calcula una sola vez: el trabajo crece de forma proporcional a $n$.

Torres de Hanói

Hay tres varillas y $n$ discos de distintos tamaños apilados en la primera. Hay que pasarlos a la tercera moviendo un disco por vez y sin poner uno grande sobre uno chico. La solución es recursiva:

1. Mover $n-1$ discos a la varilla auxiliar.

2. Mover el disco más grande a la varilla destino.

3. Mover de nuevo los $n-1$ discos sobre el más grande.

4. Caso base: con 1 disco, se mueve directamente (1 movimiento).

5. Caso recursivo: para $n$ discos se resuelve el problema con $n-1$ discos dos veces, más un movimiento.

Si $M(n)$ es el número de movimientos: $M(1) = 1$ y $M(n) = 2\,M(n-1) + 1$.

Cada disco extra duplica (y suma uno) el número de movimientos. Con 10 discos son 1,023 movimientos; con 20, más de un millón. Aunque el algoritmo es correcto y sencillo, el trabajo crece tan rápido que para muchos discos ninguna computadora lo termina en un tiempo razonable.

Volvé al principio: las 200 fichas se ordenan dividiéndolas en montones más pequeños, ordenando cada uno y juntándolos. Eso es dividir y vencer, y se apoya en la misma idea recursiva de achicar el problema hasta que sea trivial.

Resumen

• Un algoritmo recursivo se llama a sí mismo con un problema más pequeño; necesita caso base (se resuelve directo) y caso recursivo (se acerca al base).

• Para trazar, anotá cada llamada y esperá al caso base; luego las respuestas suben.

• Dividir y vencer parte el problema en subproblemas del mismo tipo y combina las soluciones.

• La eficiencia se compara contando pasos: buscar por mitades necesita unas 10 comparaciones con 1,000 datos ordenados, frente a 1,000 uno por uno.

• Una recursión puede repetir trabajo (Fibonacci) y se mejora guardando resultados o usando un ciclo; Hanói muestra que algunos algoritmos crecen muy rápido: $M(n) = 2\,M(n-1) + 1$.