Ejercicios: Recursividad y Divide y Vencerás - Programación 1

Ejercicios de Recursividad y Divide y Vencerás¶

Estos ejercicios tienen como propósito dominar la recursividad de control y el paradigma de diseño “Divide y Vencerás” en C.

Casos de corte explícitos: Definí el caso base al inicio de la función recursiva para evitar lazo de llamada infinitos y desbordamientos de stack frame (ver Regla 0x2009h: Los ejercicios deben ser resueltos mediante funciones).
Uso de recursión de cola: Cuando sea posible, estructurá las funciones recursivas utilizando parámetros acumuladores para permitir la optimización por parte del compilador.

Implementar la función factorial de forma recursiva siguiendo la definición matemática.

long int factorial(int n);

Definición recursiva:

n! = \begin{cases} 1 & \text{si } n = 0 \\ n \times (n-1)! & \text{si } n > 0 \end{cases}

(1)

Casos de prueba:

Implementar suma de dos enteros positivos usando solo recursividad (sin operador + en el paso recursivo).

int suma_recursiva(int a, int b);

Estrategia: Decrementar b e incrementar a hasta que b sea 0.

suma(a, b) = \begin{cases} a & \text{si } b = 0 \\ suma(a + 1, b - 1) & \text{si } b > 0 \end{cases}

Implementar multiplicación usando solo sumas recursivas.

int producto_recursivo(int a, int b);

a \times b = \begin{cases} 0 & \text{si } b = 0 \\ a + producto(a, b - 1) & \text{si } b > 0 \end{cases}

Complejidad: $O(b)$ en tiempo.

Implementar $base^{exponente}$ de forma recursiva.

long int potencia(int base, int exponente);

Versión básica: $O(n)$ en tiempo.

base^{exp} = \begin{cases} 1 & \text{si } exp = 0 \\ base \times potencia(base, exp - 1) & \text{si } exp > 0 \end{cases}

Desafío: Implementar versión optimizada usando exponenciación rápida (divide y vencerás) con complejidad $O(\log n)$ .

base^{exp} = \begin{cases} 1 & \text{si } exp = 0 \\ \left(base^{exp/2}\right)^2 & \text{si } exp \text{ es par} \\ base \times \left(base^{(exp-1)/2}\right)^2 & \text{si } exp \text{ es impar} \end{cases}

Implementar la secuencia de Fibonacci recursivamente.

long int fibonacci(int n);

Ecuación de recurrencia:

F(n) = \begin{cases} 0 & \text{si } n = 0 \\ 1 & \text{si } n = 1 \\ F(n-1) + F(n-2) & \text{si } n > 1 \end{cases}

(6)