Ejercicios: Recursividad y optimización de algoritmos

Explicá con tus palabras qué es un algoritmo recursivo. En tu respuesta mencioná cuáles son las dos partes que no pueden faltar en una función recursiva: el caso base y el caso recursivo.

Observá esta definición del factorial de un número natural $n$:

• $0! = 1$

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

Indicá cuál es el caso base y cuál es el caso recursivo. Luego calculá $4!$ siguiendo la definición.

Un estudiante de Ciencias de la Computación tiene que ordenar 200 fichas de inscripción de un centro escolar. Decide dividirlas en montones más pequeños, ordenar cada montón y luego juntarlos. Indicá qué estrategia de diseño de algoritmos está usando y explicá en una o dos frases por qué ayuda a resolver el problema.

Considerá esta función escrita en pseudocódigo:

función suma(n):

    si n = 1:

        devolver 1

    sino:

        devolver n + suma(n - 1)

1. a) Seguí paso a paso la ejecución de suma(4) y escribí cada llamada y el valor que devuelve.
2. b) Explicá qué calcula esta función en general.

Gabriela observa la sucesión de números: 2, 4, 8, 16, 32, ...

1. a) Describí el patrón que reconocés en la sucesión.
2. b) Escribí una definición recursiva (con caso base y caso recursivo) que permita obtener el término $n$ de la sucesión.
3. c) Calculá el sexto término usando tu definición.

Daniela debe encontrar el número de matrícula 4,350 en una lista de 1,000 estudiantes ordenada de menor a mayor. Propone dos algoritmos:

• Algoritmo A: revisar uno por uno desde el primero hasta encontrarlo.

• Algoritmo B: comparar con el elemento del medio y descartar la mitad de la lista que no sirve, repitiendo el proceso.

1. a) Indicá cuál algoritmo es más eficiente cuando la lista es grande y explicá por qué.
2. b) Estimá cuántas comparaciones necesita como máximo el algoritmo A y justificá por qué el B necesita muchas menos (te sirve saber que $2^{10} = 1,024$).

La sucesión de Fibonacci se define así:

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

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

Un estudiante implementa esta definición de forma recursiva directa para calcular $F(6)$.

1. a) Dibujá o describí el árbol de llamadas que se genera e indicá cuántas veces se calcula $F(3)$.
2. b) Explicá por qué este algoritmo es ineficiente cuando $n$ crece.
3. c) Proponé una mejora (por ejemplo, guardar resultados ya calculados o usar un ciclo) y argumentá por qué reduce el trabajo.

Josué tiene que escribir un algoritmo para el juego de las Torres de Hanói con 3 discos. La solución recursiva consiste en: mover $n-1$ discos a la varilla auxiliar, mover el disco más grande a la varilla destino y mover de nuevo los $n-1$ discos sobre el más grande.

1. a) Identificá el caso base y el caso recursivo de la estrategia.
2. b) Si $M(n)$ es el número de movimientos para $n$ discos, planteá la relación $M(n) = 2\,M(n-1) + 1$ con $M(1) = 1$ y calculá $M(3)$ y $M(5)$.
3. c) Analizá qué ocurre con el número de movimientos al agregar un disco más y explicá qué implica eso para la eficiencia del algoritmo.