Prerrequisitos y Entorno de Ejecución Requerido¶
Para compilar y verificar las soluciones de este módulo bajo el estándar C11 estricto de cátedra, se requiere:
Compilador C11: GCC 9+ o Clang 11+ configurado con flags
-Wall -Wextra -Werror -pedantic -std=c11.Entorno POSIX: Linux o WSL con utilidades estándar, soporte de llamadas a funciones y análisis de memoria.
Herramientas de Verificación: Valgrind (memcheck) y AddressSanitizer (
-fsanitize=address,undefined) para auditar la profundidad del marco de pila (stack frames) y prevenir Stack Overflow.Conocimientos Previos: Pila de llamadas en memoria, paso por valor y referencia, inducción matemática, casos de corte explícitos y aritmética de punteros en subarreglos.
Objetivos Pedagógicos y Competencias (Taxonomía de Bloom)¶
Nivel 2 (Comprensión): Analizar el ciclo de vida de los marcos de activación y la descomposición inductiva de problemas.
Nivel 3 (Aplicación): Implementar funciones recursivas elementales (aritmética, arreglos, cadenas, divide y conquista) en C11.
Nivel 4 (Análisis): Evaluar el costo de memoria en pila () frente a soluciones iterativas () y optimizaciones de recursión de cola.
Andamiaje Progresivo: Ejercicios andamiados con contratos formales (precondiciones/postcondiciones), tablas de vectores de prueba y suites ejecutables con
assert().
Capítulos de Apunte Correspondientes¶
Matemática Recursiva¶
Ejercicio 3.07.01 - Factorial ⭐⭐☆☆☆¶
```c #include <stdio.h> #include <assert.h> unsigned long long factorial_rec(unsigned int n) { if (n <= 1) { return 1ULL; } return (unsigned long long)n * factorial_rec(n - 1); } int main(void) { assert(factorial_rec(0) == 1ULL); assert(factorial_rec(1) == 1ULL); assert(factorial_rec(2) == 2ULL); assert(factorial_rec(5) == 120ULL); assert(factorial_rec(10) == 3628800ULL); return 0; } ```
(ej_b3_c07_02)=
### Ejercicio 3.07.02 - Suma Recursiva ⭐⭐☆☆☆
:::{exercise}
:label: ej_b3_c07_02_suma
Implementá la suma de dos enteros no negativos $a + b$ decrementando el segundo
operando hasta converger al caso base $b = 0$.
```c
unsigned int suma_rec(unsigned int a, unsigned int b);
```
**Tabla de Vectores de Prueba:**
| Operandos (`a`, `b`) | Salida Esperada |
| :--- | :--- |
| `a = 5, b = 0` | `5` |
| `a = 0, b = 7` | `7` |
| `a = 12, b = 8` | `20` |
::::{solution}
```c
#include <stdio.h>
#include <assert.h>
unsigned int suma_rec(unsigned int a, unsigned int b) {
if (b == 0) {
return a;
}
return suma_rec(a + 1, b - 1);
}
int main(void) {
assert(suma_rec(5, 0) == 5);
assert(suma_rec(0, 7) == 7);
assert(suma_rec(12, 8) == 20);
assert(suma_rec(0, 0) == 0);
return 0;
}
```
(ej_b3_c07_03)=
### Ejercicio 3.07.03 - Producto por Sumas Sucesivas ⭐⭐☆☆☆
:::{exercise}
:label: ej_b3_c07_03_producto
Implementá la multiplicación recursiva de dos enteros no negativos $a \times b$
mediante acumulaciones sucesivas.
```c
unsigned int producto_rec(unsigned int a, unsigned int b);
```
**Tabla de Vectores de Prueba:**
| Operandos (`a`, `b`) | Salida Esperada |
| :--- | :--- |
| `a = 4, b = 0` | `0` |
| `a = 6, b = 1` | `6` |
| `a = 7, b = 5` | `35` |
::::{solution}
```c
#include <stdio.h>
#include <assert.h>
unsigned int producto_rec(unsigned int a, unsigned int b) {
if (b == 0) {
return 0;
}
return a + producto_rec(a, b - 1);
}
int main(void) {
assert(producto_rec(4, 0) == 0);
assert(producto_rec(0, 9) == 0);
assert(producto_rec(6, 1) == 6);
assert(producto_rec(7, 5) == 35);
return 0;
}
```
(ej_b3_c07_04)=
### Ejercicio 3.07.04 - Potencia Entera ⭐⭐☆☆☆
:::{exercise}
:label: ej_b3_c07_04_potencia
Calculá $base^{exp}$ para un exponente entero no negativo de manera recursiva.
```c
long long potencia_rec(long long base, unsigned int exp);
```
**Tabla de Vectores de Prueba:**
| Entrada (`base`, `exp`) | Salida Esperada |
| :--- | :--- |
| `base = 5, exp = 0` | `1LL` |
| `base = 2, exp = 8` | `256LL` |
| `base = -3, exp = 3` | `-27LL` |
::::{solution}
```c
#include <stdio.h>
#include <assert.h>
long long potencia_rec(long long base, unsigned int exp) {
if (exp == 0) {
return 1LL;
}
return base * potencia_rec(base, exp - 1);
}
int main(void) {
assert(potencia_rec(5, 0) == 1LL);
assert(potencia_rec(2, 8) == 256LL);
assert(potencia_rec(-3, 3) == -27LL);
assert(potencia_rec(-3, 2) == 9LL);
return 0;
}
```
---
## Series Recursivas
(ej_b3_c07_05)=
### Ejercicio 3.07.05 - Fibonacci ⭐⭐☆☆☆
:::{exercise}
:label: ej_b3_c07_05_fibonacci
Calculá el n-ésimo término de Fibonacci respetando:
$F(0) = 0$, $F(1) = 1$, $F(n) = F(n-1) + F(n-2)$.
```c
unsigned long long fibonacci_rec(unsigned int n);
```
**Tabla de Vectores de Prueba:**
| Índice `n` | Fibonacci Esperado |
| :--- | :--- |
| `0` | `0ULL` |
| `1` | `1ULL` |
| `6` | `8ULL` |
| `10` | `55ULL` |
::::{solution}
```c
#include <stdio.h>
#include <assert.h>
unsigned long long fibonacci_rec(unsigned int n) {
if (n == 0) {
return 0ULL;
}
if (n == 1) {
return 1ULL;
}
return fibonacci_rec(n - 1) + fibonacci_rec(n - 2);
}
int main(void) {
assert(fibonacci_rec(0) == 0ULL);
assert(fibonacci_rec(1) == 1ULL);
assert(fibonacci_rec(2) == 1ULL);
assert(fibonacci_rec(6) == 8ULL);
assert(fibonacci_rec(10) == 55ULL);
return 0;
}
```
---
## Arreglos Recursivos
(ej_b3_c07_06)=
### Ejercicio 3.07.06 - Copiar Arreglo Recursivo ⭐⭐⭐☆☆
:::{exercise}
:label: ej_b3_c07_06_copiar_arr
Copiá los elementos de un arreglo a un búfer destino en el mismo orden usando
recursión y aritmética de punteros.
```c
void copiar_arreglo_rec(const int *origen, int *destino, size_t n);
```
**Tabla de Vectores de Prueba:**
| Arreglo Origen | `n` | Arreglo Destino Resultante |
| :--- | :--- | :--- |
| `[10, 20, 30]` | `3` | `[10, 20, 30]` |
| `[]` | `0` | Sin modificaciones |
::::{solution}
```c
#include <stdio.h>
#include <assert.h>
#include <stddef.h>
void copiar_arreglo_rec(const int *origen, int *destino, size_t n) {
if (n == 0) {
return;
}
*destino = *origen;
copiar_arreglo_rec(origen + 1, destino + 1, n - 1);
}
int main(void) {
int orig[] = {10, 20, 30, 40};
int dest[4] = {0};
copiar_arreglo_rec(orig, dest, 4);
assert(dest[0] == 10 && dest[1] == 20 && dest[2] == 30 && dest[3] == 40);
/* Caso de longitud cero */
int vacio[2] = {99, 99};
copiar_arreglo_rec(orig, vacio, 0);
assert(vacio[0] == 99 && vacio[1] == 99);
return 0;
}
```
(ej_b3_c07_07)=
### Ejercicio 3.07.07 - Invertir Arreglo Recursivo ⭐⭐⭐☆☆
:::{exercise}
:label: ej_b3_c07_07_invertir_arr
Copiá los elementos de un arreglo a un búfer destino en orden inverso usando recursión.
```c
void invertir_arreglo_rec(const int *origen, int *destino, size_t n);
```
**Tabla de Vectores de Prueba:**
| Entrada | `n` | Salida Invertida |
| :--- | :--- | :--- |
| `[1, 2, 3, 4]` | `4` | `[4, 3, 2, 1]` |
| `[42]` | `1` | `[42]` |
::::{solution}
```c
#include <stdio.h>
#include <assert.h>
#include <stddef.h>
void invertir_arreglo_rec(const int *origen, int *destino, size_t n) {
if (n == 0) {
return;
}
destino[n - 1] = *origen;
invertir_arreglo_rec(origen + 1, destino, n - 1);
}
int main(void) {
int orig[] = {1, 2, 3, 4};
int dest[4] = {0};
invertir_arreglo_rec(orig, dest, 4);
assert(dest[0] == 4 && dest[1] == 3 && dest[2] == 2 && dest[3] == 1);
int uno[] = {42};
int dest_uno[1] = {0};
invertir_arreglo_rec(uno, dest_uno, 1);
assert(dest_uno[0] == 42);
return 0;
}
```
(ej_b3_c07_08)=
### Ejercicio 3.07.08 - Suma de Elementos de un Arreglo ⭐⭐☆☆☆
:::{exercise}
:label: ej_b3_c07_08_suma_arr
Sumá todos los enteros de un arreglo de forma recursiva.
```c
long long suma_arreglo_rec(const int *arr, size_t n);
```
**Tabla de Vectores de Prueba:**
| Arreglo | `n` | Suma Esperada |
| :--- | :--- | :--- |
| `[1, 2, 3, 4, 5]` | `5` | `15LL` |
| `[-5, 10, -3]` | `3` | `2LL` |
| `[]` | `0` | `0LL` |
::::{solution}
```c
#include <stdio.h>
#include <assert.h>
#include <stddef.h>
long long suma_arreglo_rec(const int *arr, size_t n) {
if (n == 0) {
return 0LL;
}
return (long long)*arr + suma_arreglo_rec(arr + 1, n - 1);
}
int main(void) {
int a1[] = {1, 2, 3, 4, 5};
assert(suma_arreglo_rec(a1, 5) == 15LL);
int a2[] = {-5, 10, -3};
assert(suma_arreglo_rec(a2, 3) == 2LL);
assert(suma_arreglo_rec(a1, 0) == 0LL);
return 0;
}
```
---
## Cadenas Recursivas
(ej_b3_c07_09)=
### Ejercicio 3.07.09 - Palíndromo ⭐⭐☆☆☆
:::{exercise}
:label: ej_b3_c07_09_palindromo
Determiná si una secuencia de caracteres es un palíndromo comprobando los
extremos y llamando recursivamente al segmento interno.
```c
bool es_palindromo_rec(const char *inicio, const char *fin);
```
**Tabla de Vectores de Prueba:**
| Cadena | `inicio` / `fin` | Resultado Esperado |
| :--- | :--- | :--- |
| `"neuquen"` | Punteros a `'n'` y `'n'` | `true` |
| `"radar"` | Punteros a `'r'` y `'r'` | `true` |
| `"caterpillar"` | Punteros a `'c'` y `'r'` | `false` |
| `""` | `inicio > fin` | `true` |
::::{solution}
```c
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
bool es_palindromo_rec(const char *inicio, const char *fin) {
if (inicio >= fin) {
return true;
}
if (*inicio != *fin) {
return false;
}
return es_palindromo_rec(inicio + 1, fin - 1);
}
static bool verificar_palindromo(const char *str) {
size_t len = strlen(str);
if (len == 0) {
return true;
}
return es_palindromo_rec(str, str + len - 1);
}
int main(void) {
assert(verificar_palindromo(""));
assert(verificar_palindromo("a"));
assert(verificar_palindromo("neuquen"));
assert(verificar_palindromo("radar"));
assert(!verificar_palindromo("caterpillar"));
assert(!verificar_palindromo("hola"));
return 0;
}
```
(ej_b3_c07_10)=
## Ejercicio 3.07.10 - Factorial Recursivo ⭐☆☆☆☆
Implementá factorial de forma recursiva.
**Orientación:**
- Caso base: `n <= 1` retorna 1
- Caso recursivo: `n * factorial(n-1)`
- Limitación: rápido overflow para n grande
---
(ej_b3_c07_11)=
## Ejercicio 3.07.11 - Potencia Recursiva ⭐⭐☆☆☆
Calculá base^exponente recursivamente.
**Orientación:**
- Caso base: `exp == 0` retorna 1
- Caso recursivo: `base * potencia(base, exp-1)`
- Versión mejorada (siguiente ejercicio)
---
(ej_b3_c07_12)=
### Ejercicio 3.07.12 - Potencia Rápida por Divide y Vencerás ⭐⭐⭐☆☆
:::{exercise}
:label: ej_b3_c07_12_potencia_rapida
Optimizá el cómputo de la potencia entera aplicando el paradigma de divide y conquista:
- Si el exponente `exp == 0`, el resultado es `1ULL`.
- Si `exp` es par: `potencia_rapida(base, exp) = potencia_rapida(base * base, exp / 2)`.
- Si `exp` es impar: `potencia_rapida(base, exp) = base * potencia_rapida(base, exp - 1)`.
```c
unsigned long long potencia_rapida_rec(unsigned long long base, unsigned int exp);
```
La complejidad temporal resultante es $O(\log_2 \text{exp})$ en lugar de $O(\text{exp})$.
**Tabla de Vectores de Prueba:**
| Base | Exponente | Salida Esperada | Justificación |
| :--- | :--- | :--- | :--- |
| `2` | `0` | `1ULL` | Caso base exponente 0 |
| `2` | `10` | `1024ULL` | $2^{10} = 1024$ |
| `3` | `5` | `243ULL` | $3^5 = 243$ |
| `10` | `4` | `10000ULL` | $10^4 = 10000$ |
::::{solution}
```c
#include <stdio.h>
#include <assert.h>
unsigned long long potencia_rapida_rec(unsigned long long base, unsigned int exp) {
if (exp == 0) {
return 1ULL;
}
if (exp % 2 == 0) {
return potencia_rapida_rec(base * base, exp / 2);
}
return base * potencia_rapida_rec(base, exp - 1);
}
int main(void) {
assert(potencia_rapida_rec(2, 0) == 1ULL);
assert(potencia_rapida_rec(5, 1) == 5ULL);
assert(potencia_rapida_rec(2, 10) == 1024ULL);
assert(potencia_rapida_rec(3, 5) == 243ULL);
assert(potencia_rapida_rec(10, 4) == 10000ULL);
return 0;
}
```
(ej_b3_c07_13)=
### Ejercicio 3.07.13 - Suma Recursiva de Dígitos ⭐⭐☆☆☆
:::{exercise}
:label: ej_b3_c07_13_suma_digitos
Implementá una función pura que sume los dígitos de un entero no negativo de forma recursiva:
- Caso base: si $n < 10$, retorna $n$.
- Paso recursivo: $(n \pmod{10}) + \text{suma\_digitos\_rec}(n / 10)$.
```c
unsigned int suma_digitos_rec(unsigned long long n);
```
**Tabla de Vectores de Prueba:**
| Entrada $n$ | Descomposición | Retorno Esperado |
| :--- | :--- | :--- |
| `0` | Caso base | `0` |
| `7` | Caso base | `7` |
| `12345` | $5 + 4 + 3 + 2 + 1$ | `15` |
| `999` | $9 + 9 + 9$ | `27` |
::::{solution}
```c
#include <stdio.h>
#include <assert.h>
unsigned int suma_digitos_rec(unsigned long long n) {
if (n < 10ULL) {
return (unsigned int)n;
}
return (unsigned int)(n % 10ULL) + suma_digitos_rec(n / 10ULL);
}
int main(void) {
assert(suma_digitos_rec(0) == 0);
assert(suma_digitos_rec(7) == 7);
assert(suma_digitos_rec(12345) == 15);
assert(suma_digitos_rec(999) == 27);
return 0;
}
```
(ej_b3_c07_14)=
### Ejercicio 3.07.14 - Torres de Hanoi con Registro de Movimientos ⭐⭐⭐☆☆
:::{exercise}
:label: ej_b3_c07_14_hanoi
:enumerator: recursion-14
El clásico problema de las Torres de Hanoi ilustra la descomposición canónica de un problema en tres etapas recursivas:
1. Mover $n-1$ discos desde la aguja `origen` hasta la aguja `auxiliar` utilizando `destino` como pivote.
2. Mover el disco restante $n$ desde `origen` hasta `destino`.
3. Mover los $n-1$ discos desde `auxiliar` hasta `destino` utilizando `origen` como pivote.
Definí la estructura:
```c
typedef struct {
int disco;
char origen;
char destino;
} movimiento_hanoi_t;
```
Implementá la función recursiva:
```c
size_t hanoi_registrar(int n, char origen, char destino, char auxiliar, movimiento_hanoi_t *registro, size_t cap_max, size_t *indice_actual);
```
- **Invariante y Complejidad:** La cantidad exacta de movimientos mínimos para $n$ discos es siempre $2^n - 1$.
- Si `registro != NULL`, guarda cada movimiento secuencialmente si `*indice_actual < cap_max`.
- Retorna el conteo total acumulado de movimientos efectuados.
#### Tabla de Vectores de Prueba Obligatorios
| Discos $n$ | Agujas (Orig, Dest, Aux) | Movimientos Esperados ($2^n - 1$) | Primer Movimiento | Último Movimiento |
| :--- | :--- | :--- | :--- | :--- |
| `1` | `'A', 'C', 'B'` | `1` | Disco 1: A $\to$ C | Disco 1: A $\to$ C |
| `2` | `'A', 'C', 'B'` | `3` | Disco 1: A $\to$ B | Disco 1: B $\to$ C |
| `3` | `'A', 'C', 'B'` | `7` | Disco 1: A $\to$ C | Disco 1: A $\to$ C |
| `4` | `'A', 'C', 'B'` | `15` | Disco 1: A $\to$ B | Disco 1: B $\to$ C |
Solution to ej_b3_c07_14_hanoi
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72#include <stdio.h> #include <stddef.h> #include <assert.h> typedef struct { int disco; char origen; char destino; } movimiento_hanoi_t; size_t hanoi_registrar(int n, char origen, char destino, char auxiliar, movimiento_hanoi_t *registro, size_t cap_max, size_t *indice_actual) { if (n <= 0) { return 0; } size_t movs = 0; // 1. Mover n-1 de origen a auxiliar movs += hanoi_registrar(n - 1, origen, auxiliar, destino, registro, cap_max, indice_actual); // 2. Mover disco n de origen a destino if (registro != NULL && indice_actual != NULL && *indice_actual < cap_max) { registro[*indice_actual].disco = n; registro[*indice_actual].origen = origen; registro[*indice_actual].destino = destino; (*indice_actual)++; } movs++; // 3. Mover n-1 de auxiliar a destino movs += hanoi_registrar(n - 1, auxiliar, destino, origen, registro, cap_max, indice_actual); return movs; } int main(void) { movimiento_hanoi_t buffer[32]; size_t idx = 0; // Caso n = 1 -> 1 movimiento idx = 0; size_t m1 = hanoi_registrar(1, 'A', 'C', 'B', buffer, 32, &idx); assert(m1 == 1); assert(idx == 1); assert(buffer[0].disco == 1 && buffer[0].origen == 'A' && buffer[0].destino == 'C'); // Caso n = 2 -> 3 movimientos idx = 0; size_t m2 = hanoi_registrar(2, 'A', 'C', 'B', buffer, 32, &idx); assert(m2 == 3); assert(idx == 3); assert(buffer[0].disco == 1 && buffer[0].origen == 'A' && buffer[0].destino == 'B'); assert(buffer[1].disco == 2 && buffer[1].origen == 'A' && buffer[1].destino == 'C'); assert(buffer[2].disco == 1 && buffer[2].origen == 'B' && buffer[2].destino == 'C'); // Caso n = 3 -> 7 movimientos idx = 0; size_t m3 = hanoi_registrar(3, 'A', 'C', 'B', buffer, 32, &idx); assert(m3 == 7); assert(idx == 7); // Caso n = 4 -> 15 movimientos idx = 0; size_t m4 = hanoi_registrar(4, 'A', 'C', 'B', buffer, 32, &idx); assert(m4 == 15); assert(idx == 15); // Caso degenerado n <= 0 assert(hanoi_registrar(0, 'A', 'C', 'B', NULL, 0, NULL) == 0); return 0; }
Ejercicio 3.07.15 - Fibonacci Recursivo ⭐⭐⭐☆☆¶
Calculá el n-ésimo número de Fibonacci.
Orientación:
Caso base:
n <= 1retorna nCaso recursivo:
fib(n-1) + fib(n-2)Advertencia: Muy ineficiente (exponencial) para n grande
Ejercicio 3.07.16 - Fibonacci con Memoización ⭐⭐⭐⭐☆¶
Optimizá Fibonacci usando memoización (caché de resultados).
Orientación:
Array global
memo[MAX]inicializado en -1Antes de calcular:
if (memo[n] != -1) return memo[n]Después de calcular:
memo[n] = resultadoComplejidad: de O(2^n) a O(n)
Ejercicio 3.07.17 - Suma de Array ⭐⭐☆☆☆¶
Sumá elementos de un array recursivamente.
Orientación:
Caso base: array vacío (
n == 0) retorna 0Caso recursivo:
arr[0] + suma(arr+1, n-1)O con índices:
arr[i] + suma(arr, i+1, n)
Ejercicio 3.07.18 - Búsqueda Binaria Recursiva ⭐⭐⭐☆☆¶
Implementá búsqueda binaria de forma recursiva.
Orientación:
Caso base: rango vacío (
inicio > fin) retorna -1Calcular
medio = (inicio + fin) / 2Si
arr[medio] == objetivo: retornar medioSi
arr[medio] > objetivo: buscar en mitad izquierdaSi
arr[medio] < objetivo: buscar en mitad derecha
Ejercicio 3.07.19 - Máximo en Array ⭐⭐⭐☆☆¶
Encontrá el máximo de un array recursivamente.
Orientación:
Caso base: array de 1 elemento retorna ese elemento
Caso recursivo:
max(arr[0], maximo(arr+1, n-1))Divide y conquista: dividir en mitades y comparar máximos
Ejercicio 3.07.20 - Palíndromo Recursivo ⭐⭐⭐☆☆¶
Verificá si un string es palíndromo recursivamente.
Orientación:
Caso base: string vacío o de 1 carácter: true
Comparar primer y último carácter
Si iguales: recursión en substring sin extremos
Si diferentes: false
Ejercicio 3.07.21 - Torre de Hanoi ⭐⭐⭐⭐☆¶
Resolvé el problema de la Torre de Hanoi.
Reglas:
Mover N discos de origen a destino usando auxiliar
Solo un disco a la vez
Nunca poner disco grande sobre uno pequeño
Orientación:
1 2 3 4 5 6 7 8 9 10 11 12 13void hanoi(int n, char origen, char destino, char auxiliar) { if (n == 1) { mover(origen, destino); } else { hanoi(n - 1, origen, auxiliar, destino); mover(origen, destino); hanoi(n - 1, auxiliar, destino, origen); } }
Ejercicio 3.07.22 - Permutaciones ⭐⭐⭐⭐⭐¶
Generá todas las permutaciones de un string.
Orientación:
Para cada posición, probá cada carácter restante
Intercambiá carácter actual con cada uno de los siguientes
Recursión en resto del string
Al retornar, deshacé el intercambio (backtracking)
Ejercicio 3.07.23 - Subconjuntos (Power Set) ⭐⭐⭐⭐⭐¶
Generá todos los subconjuntos de un conjunto.
Orientación:
Para cada elemento: está o no está en el subconjunto
Dos llamadas recursivas: con elemento y sin elemento
Caso base: conjunto vacío
Total: 2^n subconjuntos
Ejercicio 3.07.24 - MergeSort ⭐⭐⭐⭐⭐¶
Implementá ordenamiento MergeSort.
Algoritmo:
Dividir array en dos mitades
Ordenar recursivamente cada mitad
Fusionar (merge) las mitades ordenadas
Orientación:
Caso base: array de 0 o 1 elemento
Función auxiliar
mergepara fusionarComplejidad: O(n log n)
Ejercicio 3.07.25 - QuickSort ⭐⭐⭐⭐⭐¶
Implementá ordenamiento QuickSort.
Algoritmo:
Elegir pivote
Particionar: menores a izquierda, mayores a derecha
Ordenar recursivamente cada partición
Orientación:
Caso base: array de 0 o 1 elemento
Función
particionarretorna posición del pivoteComplejidad promedio: O(n log n)
Ejercicio 3.07.26 - N Reinas ⭐⭐⭐⭐⭐¶
Resolvé el problema de las N reinas (colocar N reinas en tablero N×N sin que se ataquen).
Orientación:
Colocá reina fila por fila
Para cada fila, probá cada columna
Verificá si la posición es segura (no ataca a otras)
Si llegás a la última fila: solución encontrada
Backtracking si no hay posición válida
Ejercicio 3.07.27 - Laberinto (Path Finding) ⭐⭐⭐⭐⭐¶
Encontrá camino en un laberinto desde inicio a fin.
Orientación:
Matriz de 0s (libre) y 1s (pared)
Desde posición actual, probá 4 direcciones (arriba, abajo, izq, der)
Marcá visitados para evitar ciclos
Si llegás a destino: true
Backtracking: desmarcá visitado al retornar
Ejercicio 3.07.28 - Combinaciones (n choose k) ⭐⭐⭐⭐⭐¶
Generá todas las combinaciones de k elementos de un conjunto de n.
Orientación:
Elegir elemento actual o no elegirlo
Si elegís: k-1 elementos restantes
Si no elegís: k elementos de n-1 restantes
Caso base: k==0 (solución completa) o n<k (imposible)
Ejercicio 3.07.29 - Sudoku Solver ⭐⭐⭐⭐⭐¶
Resolvé un Sudoku usando backtracking.
Orientación:
Encontrá primera celda vacía
Probá números del 1 al 9
Para cada número, verificá si es válido (fila, columna, subcuadro 3×3)
Si válido: colocá número, recursión en siguiente celda
Si recursión falla: deshacé (backtracking), probá siguiente número
Caso base: no hay celdas vacías (solución encontrada)
Ejercicio 3.07.30 - s Adicionales ⭐⭐☆☆☆¶
Ejercicio 3.07.31 - Coeficiente Binomial ⭐⭐⭐☆☆¶
Calculá C(n,k) = n! / (k! × (n-k)!) recursivamente.
Orientación:
Identidad de Pascal:
C(n,k) = C(n-1,k-1) + C(n-1,k)Casos base:
C(n,0) = 1,C(n,n) = 1
Ejercicio 3.07.32 - GCD (MCD) Recursivo ⭐⭐☆☆☆¶
Implementá algoritmo de Euclides recursivamente.
Orientación:
Caso base:
b == 0retorna aCaso recursivo:
gcd(b, a % b)
Ejercicio 3.07.33 - Árbol de Expresión ⭐⭐⭐⭐⭐¶
Evaluá una expresión matemática representada como árbol binario.
Orientación:
Nodos hoja: números
Nodos internos: operadores (+, -, *, /)
Evaluación postorden: evaluar izquierdo, derecho, aplicar operador
Notas Finales¶
Estas consignas cubren desde recursión básica hasta algoritmos avanzados de backtracking y divide y conquista, desarrollando pensamiento recursivo esencial.