AALIE

Introducción al análisis recursivo

Los algoritmos recursivos requieren una lectura distinta a los algoritmos iterativos. En lugar de contar únicamente repeticiones de ciclos, se analiza cómo una función se llama a sí misma, qué tamaño tienen los subproblemas y cuándo se llega al caso base. En este módulo se usará Fibonacci como ejemplo.

Fibonacci recursivo

fibonacci(n) BEGIN
  IF n <= 1 THEN BEGIN
    RETURN n;
  END
  RETURN fibonacci(n - 1) + fibonacci(n - 2);
END

Seleccionar métodos de recurrencia

Al presionar Analizar, AALIE puede abrir una ventana para seleccionar métodos de análisis de recurrencias. No todos los métodos sirven para todas las recurrencias. Por ejemplo, el Teorema Maestro no es adecuado para Fibonacci clásico porque la recurrencia no tiene la forma estándar T(n) = aT(n/b) + f(n).

Modal de selección de métodos de recurrencia para Fibonacci.

Selección cuidadosa

No fuerces un método solo porque lo conoces. Primero revisa si la recurrencia cumple las condiciones necesarias. Un método no aplicable puede llevar a una explicación elegante pero matemáticamente incorrecta.

El método de árbol de recursión permite visualizar cómo se expanden las llamadas recursivas. En Fibonacci, cada llamada genera dos nuevas llamadas, salvo cuando se llega al caso base. Esto produce una expansión amplia, donde gran parte del trabajo se concentra hacia las hojas del árbol.

Método de árbol de recursión aplicado a Fibonacci.

El método de iteración expande la recurrencia paso a paso para observar su patrón de crecimiento. En casos como Fibonacci, puede ofrecer una aproximación o una lectura útil, pero no siempre entrega una forma exacta tan limpia como otros métodos.

Método de iteración aplicado a Fibonacci.

La ecuación característica es más adecuada para recurrencias lineales con desplazamientos constantes, como ocurre en Fibonacci. Este método permite obtener una descripción más precisa del crecimiento y conectar el resultado con la estructura algebraica de la recurrencia.

Ecuación característica aplicada a Fibonacci.

Idea clave

Fibonacci recursivo es un buen ejemplo para mostrar por qué una solución correcta puede ser ineficiente. La función calcula repetidamente subproblemas que ya había resuelto antes. Por eso la plataforma puede sugerir una lectura relacionada con programación dinámica: guardar resultados evita recomputar las mismas llamadas.

Árbol real y seguimiento

AALIE también puede mostrar un árbol real de llamadas. Esta vista no es exactamente lo mismo que el árbol teórico usado para razonar sobre la recurrencia. El árbol real representa la ejecución concreta del algoritmo con un valor específico de entrada.

Para observar la ejecución de forma controlada, usa el seguimiento paso a paso con n = 4. Avanza manualmente o usa reproducción automática. Durante la simulación verás cómo se crean llamadas recursivas, cómo llegan al caso base y cómo retornan valores hacia las llamadas anteriores.

Seguimiento paso a paso de Fibonacci con n = 4.

Claves de la recursión

En recursión, siempre identifica cuatro elementos antes de confiar en una conclusión: caso base, reducción del problema, número de llamadas recursivas y trabajo adicional fuera de las llamadas.