# Laboratorio de la semana 9: recursión en arreglos y cadenas Son dos sesiones, y cada una está pensada para unos 90 minutos de trabajo. Los comandos se corren desde `code/week-09`. Las ideas están en los apuntes, en la sección "El laboratorio, paso a paso". | Archivo | Qué es | ¿Lo cambian? | |---|---|---| | `power_frames.c` | `power(2, 3)` para mirar en `gdb` | No | | `recursion.h` | Lo que promete cada función de la sesión 1 | No | | `recursion.c` | Las cinco funciones de la sesión 1, por escribir | **Sí** | | `recursion_tests.c` | Sus pruebas con `assert` | **Sí** | | `counted.h` | Lo que promete cada función de la sesión 2, y cómo se cuenta | No | | `counted.c` | `power_slow` y `linear_search` hechas; `power_fast` y `binary_search` por escribir | **Sí** | | `merge_sort.h` | Lo que promete `merge_sort` | No | | `merge_sort.c` | `merge`, `sort_range` y `merge_sort`, por escribir | **Sí** | | `demo.c` | Compara las llamadas de cada versión | No | | `overflow.c` | Una suma con un error, y una suma demasiado profunda | Solo el caso base de `sum_by_twos` | ```sh make lab # compila recursion_tests, demo y overflow en build/lab/ build/lab/recursion_tests # corre sus pruebas build/lab/demo # compara las llamadas, en la sesión 2 make test-lab # comprueba todo el laboratorio; falla hasta que terminen ``` Todo se compila con ASan y UBSan, salvo lo que se mira en `gdb`. `recursion.c` y `counted.c` no pueden usar `for`, `while` ni variables globales: `make test-lab` revisa los ciclos. ## Sesión 1 ### Parte 1: los marcos de `power(2, 3)` (unos 20 minutos) Lean `power_frames.c` y, **sin ejecutar nada**, dibujen en papel la pila en el momento en que la llamada del caso base va a devolver. Cada marco lleva `base`, `n` y `rest`, y dice en qué línea quedó esperando. Luego compilen y compruébenlo: ```sh gcc -Wall -Wextra -std=c17 -g -O0 lab/power_frames.c -o build/power_frames_gdb gdb -q build/power_frames_gdb ``` Dentro de `gdb`, pongan un breakpoint condicional que se detenga solo en el caso base, corran, y pidan `backtrace`. Con `frame` e `info args`, revisen el marco de `n = 2`. Con `finish`, vean qué devuelve el caso base. Luego respondan por escrito: 1. ¿Cuántos marcos de `power` hay? ¿Y cuántos habría con `power(2, n)`? 2. ¿En qué línea están detenidos los marcos intermedios? ¿Por qué esa, y no otra? 3. ¿Qué valor tiene `rest` en el marco de `n = 2` antes de que vuelva la llamada? Mírenlo con `info locals`. ¿Por qué no pueden contar con ese valor? ### Parte 2: cinco funciones sin ciclos (unos 70 minutos) Lean `recursion.h`. Escriban en `recursion.c`, en este orden, y corran sus pruebas después de cada una: 1. `array_sum` 2. `array_max` 3. `count_char` 4. `is_palindrome`, con una función auxiliar `static` 5. `reverse_string`, con otra auxiliar Antes de escribir cada una, respondan las tres preguntas de los apuntes: cuál es el caso base, qué baja en cada llamada, y qué hace esta llamada con la respuesta de la siguiente. Agreguen a `recursion_tests.c` una función de prueba por cada función, con `test_array_sum` como modelo: primero los casos más pequeños. Para `reverse_string`, el texto debe estar en un arreglo, como `char s[] = "Lima";`, porque una cadena literal no se puede modificar. Y por escrito: ¿cómo saben que `is_palindrome` termina, tanto con largo par como con largo impar? **Si no alcanza el tiempo:** lo que no terminen lo terminan antes de la próxima sesión. `reverse_string` es la más larga, y ninguna otra depende de ella. ## Sesión 2 ### Parte 3: contar llamadas (unos 30 minutos) Lean `counted.h`, y `power_slow` y `linear_search` en `counted.c`. Fíjense en cómo se cuenta: `calls` apunta a un contador de quien llama, y todos los marcos reciben la misma dirección. 1. Escriban `power_fast`. El caso base es `n == 0`. Guarden el resultado de la llamada en una variable: llamar dos veces da el mismo resultado, y mucho más trabajo. 2. Escriban `binary_search`, con una auxiliar recursiva sobre el rango `[lo, hi)`. Corran `build/lab/demo` y comparen con los apuntes. Respondan por escrito, primero contando a mano, y luego comprobándolo con un cambio temporal en `demo.c`: 3. ¿Cuántas llamadas hace `power_fast` con `n` igual a 1000? ¿Y con 1024? 4. ¿Por qué `demo.c` usa `power(1, 1024)` y no `power(2, 1024)`? ¿Qué mostraría UBSan? 5. Si el arreglo de `demo.c` tuviera el doble de elementos, ¿cuántas llamadas más haría cada búsqueda? ### Parte 4: `merge_sort` (unos 40 minutos) Lean `merge_sort.h` y escriban `merge_sort.c`: 1. `merge`: mezcla dos mitades ordenadas. Sigan el pseudocódigo de los apuntes. Aquí sí se puede usar un ciclo. 2. `sort_range`: el caso base y dos llamadas. Son pocas líneas, y no reservan memoria. 3. `merge_sort`: atiende los arreglos de menos de 2 elementos, reserva `scratch`, revisa que `malloc` haya funcionado, llama a `sort_range` y libera. Al terminarla, borren las líneas `(void)` que queden. `build/lab/demo` termina con el arreglo antes y después de ordenar. Respondan por escrito: 6. ¿Quién es owner de `scratch`? ¿Quién podría liberarlo por error, y qué mostraría ASan? 7. ¿Qué pasaría si `merge` no copiara de vuelta el resultado a `a`? Pruébenlo. ### Parte 5: provocar un stack overflow (unos 20 minutos) Esta parte es corta y se puede terminar antes de la próxima clase si no alcanza el tiempo. 1. Corran `build/lab/overflow twos 10`, y luego `build/lab/overflow twos 11`. Lean el informe de ASan: ¿qué error da, en qué función y en qué línea? ¿Por qué se repite esa línea? 2. Compilen sin sanitizers y mírenlo en `gdb`: ```sh gcc -Wall -Wextra -std=c17 -g -O0 lab/overflow.c -o build/overflow_gdb gdb -q build/overflow_gdb ``` Dentro de `gdb`, usen `run twos 11` y `backtrace 3`. ¿Qué dicen los valores de `n` sobre el error? 3. Corrijan el caso base de `sum_by_twos`, de modo que cumpla lo que promete su comentario. 4. Busquen el límite de `sum_to`: corran `build/lab/overflow sum N` con distintos `N`, partiendo el rango por la mitad, hasta tener el valor con una precisión de unos 1000. Anótenlo, y digan cuántos bytes ocupa cada marco según ese número y `ulimit -s`. Ese número es de su máquina. Al final, `make test-lab`. ## Si sobra tiempo 1. Escriban `array_max` de otra forma: partan el arreglo en dos mitades, y devuelvan el mayor de los dos máximos. Cuenten cuántos marcos quedan apilados como máximo con un millón de elementos, frente a la versión que quita un elemento a la vez. 2. Escriban `is_palindrome_text`, que ignore los espacios: `"anita lava la tina"` es un palíndromo.