Ejercicios resueltos de Recursión

Question 1

Torres de Hanói: hay que pasar 4 discos de la varilla A a la C usando la B, moviendo un disco a la vez y sin poner nunca un disco grande sobre uno más pequeño. ¿Cuántos movimientos mínimos hacen falta y de dónde sale ese número?

Accepted Answer

La clave es no pensar en los 4 discos a la vez, sino en el más grande. Para que el disco 4 pueda pasar de A a C, la varilla C tiene que estar vacía y los otros 3 discos tienen que estar todos apilados en B. No hay otra manera. Eso parte el problema en tres partes: mover 3 discos de A a B, mover el disco grande de A a C (un solo movimiento) y mover esos 3 discos de B a C. «Mover 3 discos» es el mismo problema, más pequeño: ahí está la recursión. La relación queda T(n) = 2·T(n − 1) + 1. El caso base es T(1) = 1: un solo disco se mueve directo. Sin ese caso base la definición se llamaría a sí misma para siempre. Se sube desde el caso base: T(2) = 2 × 1 + 1 = 3. T(3) = 2 × 3 + 1 = 7. T(4) = 2 × 7 + 1 = 15. El patrón cerrado es T(n) = 2ⁿ − 1, y para n = 4 da 2⁴ − 1 = 15. También explica por qué esta recursión cuesta O(2ⁿ): con 20 discos ya son 1.048.575 movimientos. Respuesta: 15 movimientos. Salen de T(n) = 2·T(n − 1) + 1 con T(1) = 1, que se cierra en T(n) = 2ⁿ − 1.

Question 2

El algoritmo de Euclides se define así: mcd(a, b) = mcd(b, a mod b), con caso base mcd(a, 0) = a. Rastrea las llamadas para mcd(1071, 462).

Accepted Answer

Antes de rastrear, por qué funciona: cualquier número que divida a la vez a y b divide también el residuo a mod b, así que el máximo común divisor no cambia al reemplazar el par (a, b) por (b, a mod b). Y por qué termina: el residuo siempre es menor que b, así que el segundo argumento se achica en cada llamada y el caso base b = 0 se alcanza seguro. Llamada 1: mcd(1071, 462). 1071 = 2 × 462 + 147, el residuo es 147. Se llama a mcd(462, 147). Llamada 2: mcd(462, 147). 462 = 3 × 147 + 21, el residuo es 21. Se llama a mcd(147, 21). Llamada 3: mcd(147, 21). 147 = 7 × 21 + 0, el residuo es 0. Se llama a mcd(21, 0). Llamada 4: b = 0, es el caso base, y devuelve 21. Ese 21 sube tal cual por las tres llamadas que estaban esperando, porque ninguna le hace nada al resultado antes de devolverlo. Comprobación: 1071 ÷ 21 = 51 y 462 ÷ 21 = 22, y 51 y 22 ya no tienen divisores comunes. Respuesta: mcd(1071, 462) = 21, alcanzado en 4 llamadas.

Recursión