GUÍA 09-09-26 Estructuras de Datos

CN122 · miércoles 09/09/2026 · 13:00-14:15 · Sesión 10

Recursión y su relación con la pila · Torres de Hanói

RECURSIÓN

Una función recursiva se llama a sí misma con un problema más pequeño. Necesita dos cosas y ninguna es opcional: un caso base que la detiene y un paso recursivo que se acerca al caso base.

QUÉ PASA EN MEMORIA

Cada llamada crea un marco en la pila del programa con sus parámetros, sus variables locales y la dirección de retorno. La recursión no es magia: es la pila del sistema haciendo el trabajo que harías a mano.

Por eso la recursión sin caso base produce desbordamiento de pila, y por eso una recursión muy profunda puede fallar aunque sea correcta.

TORRES DE HANÓI

Mover n discos de A a C usando B, sin poner nunca un disco grande sobre uno pequeño.

• Caso base: n = 1, mover el disco directamente.
• Paso: mover n−1 de A a B, mover el disco n de A a C, mover n−1 de B a C.

La solución completa cabe en tres líneas y es prácticamente imposible de escribir iterativamente sin simular una pila. Es el mejor argumento a favor de la recursión.

EL COSTO

T(n) = 2T(n−1) + 1, cuya solución es 2ⁿ − 1 movimientos. Con 64 discos y un movimiento por segundo tomaría más de quinientos mil millones de años. La recursión es elegante, no barata.

RECURSIÓN DE COLA

Si la llamada recursiva es la última operación, algunos compiladores la convierten en un ciclo y eliminan el crecimiento de la pila. En C con optimización activada suele ocurrir, pero no está garantizado por el estándar.

CUÁNDO CONVERTIR A ITERATIVO

• Si la profundidad puede ser grande y hay riesgo de desbordamiento.
• Si hay recálculo exponencial, como en Fibonacci ingenuo.
• Si el desempeño importa más que la claridad. En caso contrario, la recursión suele ser más legible.

PRÁCTICA

Hanói con impresión de movimientos y conteo; factorial y Fibonacci recursivo e iterativo, comparando tiempos.