[Bottom-up][Taller Recursión 8086][Parte b]

[Bottom-up][Taller Recursión 8086][Parte b]

de Ignacio Rafael Ferreira Urrutia -
Número de respuestas: 2

Buenas, tenía una consulta con la parte b, antes de hacer una llamada recursiva el stack me quedó de la siguiente forma:

he

Entonces por cada llamada preciso lugar para 8 words a almacenar en el stack, hice la recursión,

buscarabb(0)=16

buscarabb(n)=16+buscarabb(n-1)

Entonces buscarabb(10)=16*11? o estoy contando una llamada de más?.

Con el tamaño del arreglo como cada elemento del árbol ocupa 2 bytes, si el árbol fuera completo:

cantbytes(abb)=2^(altura(abb)+1)bytes?

Es equivalente ver el peor caso con una lista que con un árbol completo para ver la cantidad de espacio necesario en el stack ya que toma va siempre hacia una rama sola?.

Si alguien tiene idea o ya lo hizo le agradezco.

Saludos

En respuesta a Ignacio Rafael Ferreira Urrutia

Re: [Bottom-up][Taller Recursión 8086][Parte b]

de Aldo Martin Plazzotta Aguilera -
Estimado: no tengo una solución corregida del ejercicio, pero comparto un par de consideraciones sobre el problema (ni hablar que puedo estar equivocado en algo)

Si entendí bien, la figura que mostras se corresponde al consumo de stack para la ejecución de un caso base (es decir: un caso en el cual no se realiza una llamada recursiva)

De ser así, la primer ecuación esta bien:    consumo(0) = 16

Ahora para el caso recursivo, de tener que hacer la llamada recursiva a la funcion tendrías que agregar otras cosas más al stack (además de las 8 words del caso base)

En concreto tendrías que agregar al menos: arbol, nuevo indice, valor e IP de retorno (esta ultima la agrega el CALL recursivo)

Por lo tanto, antes del llamado recursivo en el stack tenes las 8 words del caso base mas 4 words del llamado recursivo:

la ecuacion sería : consumo(n) = 24 + consumo(n-1)

Habria que resolver el sistema 

consumo(0) = 16
consumo(n) = 24 + consumo(n-1)

Por último, es acertada la observación que haces, la busqueda se hace sobre una unica rama. Por lo tanto el consumo de stack depende mas bien de la altura del arbol y no de la cantidad de nodos (mas alla si el arbol es completo o no)

Ejemplos:
A) arbol con un solo elemento, altura = 1       
B) Arbol vacio, altura = 0
C) arbol que degenera en lista con 3 elementos, altura = 3

A)       5                               B)      -1                 C)            5
         /   \                                                                        /   \
      -1    -1                                                                     4    -1
                                                                                   /   \
                                                                                 3 
                                                                               /   \
                                                                             -1   -1

Entonces las ecuaciones en recurrencia deberían depender de la altura "h" y no de "n"

Caso base (arbol vacio) : consumo(0) = 16

caso recursivo (arbol altura h >=1 ):      consumo(h) = 24 + consumo(h-1)   (suponiendo que 24 es el consumo necesario para evaluar si un elemento es igual a valor)

Saludos.