Saltar a contenido

Ejercicios · PFC · Recursion de cola y procesos

Nueve ejercicios para recorrer en el navegador, tres por cada tema de la sesión y en su mismo orden. La mecánica es la de siempre: prediga antes de ejecutar, avance paso a paso y busque qué se conserva mientras todo lo demás cambia.

Lo que se conserva en esta sesión es el valor: las tres versiones del factorial dan lo mismo. Lo que cambia es el proceso que generan, y ese proceso se mide con dos números que se confunden todo el tiempo, cuántas vueltas da y cuánto deja esperando. Los nueve ejercicios son maneras de separar esos dos números.

Funciones frente a procesos

contar

factorial(n) con la pila dibujada: una caja por multiplicación que espera. La predicción pide cuántas multiplicaciones hará; la respuesta es n, y el contador del else la confirma en la bajada. Lo que hay que mirar es el paso en que la pila llega a su punto más alto, porque ahí también hay n cajas: en esta función tiempo y espacio coinciden, y por eso es fácil confundirlos.

reducir

El modelo de sustitución sobre una función recursiva, un reemplazo por vuelta con el trozo que cambia resaltado. La expresión crece mientras baja y encoge mientras sube, y la subida siempre resuelve la operación más interna, que es la única con dos valores. Compare factorial(3) con factorialAlFinal(3): el * está en lados distintos y el proceso es el mismo. sumaLineal(2, 5) deja además ver los pred reduciéndose antes de entrar, por valor.

agotar

Cuatro llamadas con n = 100000, y una sola pregunta para cada una: ¿qué se acaba, el tiempo, el espacio o nada? Dos revientan la pila, una gira sin fin y una termina. Lo que las separa no es cuántas vueltas dan sino qué dejan esperando alrededor de la llamada. Los cuatro resultados son de correr el código; el que termina devuelve 0 por desborde del Int, que es otro problema.

Recursión lineal e iteración

pendientes

factorial y fact corriendo lado a lado sobre la misma entrada, cada una con su pila de marcos dibujada debajo. Cada marco dice qué tiene adentro: a la izquierda los de abajo esperan su multiplicación —espera 4 * ___— y el de arriba está entrando o acaba de recibir el valor del que se cerró y hace su cuenta. Ninguno se cierra hasta que el de abajo devuelve, y en el punto más hondo hay n + 1 abiertos al tiempo. A la derecha la caja es una sola, con borde doble, y dice a quién reemplazó y qué calculó antes de llamar. El tercer preset hace lo mismo con sumaLineal y sumaIter, que es el ejercicio de la sesión.

acumulador

La traza de factIter como tabla, una fila por llamada. Se llena la columna prod de memoria y después se ve la ejecución llenarla. La regla que hay que descubrir es que el prod de una fila es cont × prod de la fila de arriba: el resultado se arma antes de llamar y viaja como argumento, y por eso al volver no queda nada por hacer.

cola

Cinco versiones de factIter. Las cinco dan 720 para n = 6; para n = 100000 solo dos terminan. Hay que marcar cuáles siguen siendo de cola. Tres la rompen sin que se note —sumar y restar lo mismo, multiplicar después de volver, envolver la llamada en math.max— y una parece romperla y no: un val calculado antes de llamar. Es el ejercicio más exigente de la sesión.

Recursión de árbol

árbol

producto(i, j) parte el rango por la mitad y el proceso deja de ser una fila. El árbol se dibuja con sus ramas, y cada nodo lleva el número del orden en que se abrió: amarillo mientras su marco está abierto, verde con su valor cuando cerró. La rama gruesa es el camino de la raíz al marco actual, que es exactamente lo que hay en la pila de al lado, con los mismos números y con lo que cada marco espera. Hay dos predicciones y dan números distintos: las llamadas en total, 2n − 1, y los marcos abiertos al mismo tiempo como máximo, que son los niveles del árbol. Lo que hay que mirar es la pila bajando a uno cuando termina la rama izquierda, antes de subir por la derecha: siete llamadas y nunca más de tres abiertas.

cuentas

La tabla que cierra la sesión, vacía: para un n dado, llamadas y hondura de factorial, fact y factArbol. Seis casillas que se llenan de memoria y se comprueban contra la simulación. Las tres son funciones recursivas y solo una genera un proceso iterativo.

caso base

Cuatro versiones de producto que difieren solo en los casos base. Una es la de la sesión; de las otras tres, una no termina, una termina con el valor equivocado, y una da 24 para producto(1, 5) igual que la correcta y aun así está mal. Esa última se delata en producto(3, 3), un caso que el programa grande no visita nunca.