Recursión – pila de llamadas y árbol de llamadas

Qué muestra

Una función recursiva resuelve un problema llamándose a sí misma con una versión más pequeña del mismo problema. Cada llamada apila un nuevo marco en la pila de llamadas; el caso base devuelve un valor sin volver a llamar, y luego los marcos se desapilan mientras los valores suben. El árbol de llamadas muestra todas las llamadas: factorial y la suma de una lista forman una sola cadena, mientras que Fibonacci, el ordenamiento por mezcla y la torre se ramifican. Fibonacci simple repite las mismas llamadas, así que su número crece exponencialmente; la memoización guarda los resultados. Sin caso base, la pila se desborda.

Cómo usarla

Elige una Función y ajusta n (o el Objetivo en la búsqueda binaria). Pulsa Paso para hacer una llamada o un retorno cada vez, Atrás para deshacer un paso o Ejecutar para reproducir a la Velocidad elegida. Observa el código, la pila y el árbol; toca un nodo para ver detalles. Marca Memo en Fibonacci o desmarca Con caso base para ver un desbordamiento de pila.

Parámetros que puedes cambiar

• Función recursiva Factorial n!, Números de Fibonacci, Suma de una lista, Búsqueda binaria, Torre de discos (rompecabezas), Ordenamiento por mezcla
• n (tamaño del problema) 0–8
• Valor buscado (búsqueda binaria) 0–100
• Memoización (Fibonacci)
• Incluir el caso base
• Lenguaje Python, Pseudocódigo
• Velocidad 0,5–10 pasos/s

Preguntas para explorar

1. ¿Cuántas veces se llama a fib(2) al calcular fib(6) sin memoización, y cuántas con ella?
2. ¿Cuál es la profundidad máxima de la pila para factorial(5), y cuánta pila necesita la versión con bucle?
3. ¿Por qué quitar el caso base provoca un desbordamiento de pila y no una respuesta incorrecta?