← Volver a los ejercicios

Una función recursiva sobre [n izq der], llamado por llamado

Un árbol es la lista vacía o una lista con el valor del nodo y sus dos subárboles. contarNodos y altura siguen esa gramática renglón por renglón y se diferencian en dos cosas: cuánto vale el caso base y qué se hace con lo que devuelven los dos subárboles. Aquí se ejecutan paso a paso, con la pila de llamados a la vista.

1. El árbol, la función y la predicción

En ámbar, el subárbol que recibió el llamado en curso. En verde, los nodos cuyo llamado ya devolvió, con el valor devuelto encima.
¿Cuántas veces se ejecuta la línea del caso base en toda la corrida?

2. Ejecute el código

Las dos funciones están en el panel. El contador de cada línea dice cuántas veces se ejecutó, y las líneas de la función que no se está corriendo se quedan en cero.

Paso 0 de 0

3. La pila de llamados

El llamado de arriba es el que se está ejecutando. Cada marco guarda su propio A y su propio ans, y solo desaparece cuando devuelve.

4. Lo que cuesta

5. Para llevarse

Sin solución aquí. Corra altura sobre el árbol en fila y mire hasta dónde llega la pila; después diga cuántos marcos tendría con mil nodos en fila y qué pasa en Python cuando eso ocurre. Escriba además qué devolvería altura si el caso base valiera 0 en vez de −1, con el árbol de un solo nodo como prueba.