4

tengo una función recursiva que calcula el numero de nodos que tiene un árbol binario, obviamente funciona bien, pero hay una cosa que no entiendo.

#include <iostream>
#include "abinCeldasEnlazadas.h"

using namespace std;

template <typename T>
int numNodos (const Abin<T>& A)
{
    int cont = 0;
    if(A.arbolVacioB())
    {
        return cont;
    }
    else
    {
      cont = calculaNodos (A.raizB(), A, 1);
    }
 return cont;
}

template <typename T>
int calculaNodos (typename Abin<T>::nodo n,const Abin<T>& arbol, int contador)
{
     if(arbol.hijoIzqdoB(n) != arbol.NODO_NULO)
     {
      contador = calculaNodos(arbol.hijoIzqdoB(n),arbol,contador+1);
     }

     if (arbol.hijoDrchoB(n) != arbol.NODO_NULO)
         {
          contador =  calculaNodos (arbol.hijoDrchoB(n), arbol, contador+1);
         }
 return contador;
}

Va en preorden, ya sabéis, primero raíz, luego visita hijo izquierdo y luego hijo derecho. La cuestión es que cuando lo he estado realizando, si por ejemplo tenemos este árbol:

Arbol Binario

Lo que hace es:

  1. Comprueba que el árbol no está vacío, entonces, en la primera función, se va al else directamente ya que el árbol tiene raíz.
  2. Empieza la recursividad, se le pasa la raíz, el árbol y el contador a 1 (ya que como mínimo tiene 1 nodo que es el raíz).
  3. Comenzamos la segunda función, como tiene hijo izquierdo que es 7 y no es un nodo nulo, llama de nuevo a calculaNodos con el nodo 7, el árbol, y el contador a 2 (ya tenemos 1 nodo raíz, y 1 nodo que es 7, en total, 2 nodos).
  4. Vuelve a llamarse recursivamente, y resulta que vuelve a tener hijo izquierdo, que es el 2 y no es nodo nulo, de nuevo llamamos a calculaNodos con el nodo 2, el árbol, y el contador a 3 (total 3 nodos, raíz, 7 y 2).

AQUÍ VIENE MI DUDA:

5.Se llama recursivamente de nuevo y ya el nodo 2 no tiene ni hijo izquierdo ni hijo derecho, es decir, en calculaNodos, salta el primer if y el segundo if, y devuelve contador.

Mi duda es, funcionar el programa me funciona perfectamente, pero lo que no entiendo es cómo si devuelve ahí contador, el programa sigue contando hijo derecho de 7 que sería el 6, pero si ya antes ha devuelto el contador... Es decir, ¿cómo funciona ahí la recursividad para que siga leyendo el hijo derecho de 7 (que es 6) si ya antes, ha devuelto contador y ha acabado.

Muchas gracias.

1 respuesta 1

5

Fíjate que cuando haces una llamada recursiva, en realidad estás llamando a otra función (aunque en este caso particular la función a la que llames sea la misma). La función que hizo la llamada será reanudada más tarde, cuando la función a la que llamaste retorne.

Así pues, la primera vez que llamas a CalculaNodos desde numNodos pasándole el raíz (nodo 2), esta última se quedará esperando a que CalculaNodos termine y le retorne su resultado. Llamemos llamada 0 a esta primera llamada.

Pero CalculaNodos, a su vez llama a CalculaNodos pasándole el nodo 7, y se queda a la espera de su resultado. Llamemos llamada 1 a esta segunda llamada.

Este CalculaNodos llama otra vez a CalculaNodos (llamada 2) pasándole el nodo 2, y queda a la espera del resultado.

Aquí llegamos por fin a una llamada que no hace más llamadas recursivas. Esta última llamada retorna 3 tal como tú calculaste, pero ¿a quién le retorna ese 3? A quien hizlo la llamada 2. Por tanto nos encontramos de nuevo dentro de la función CalculaNodos cuando estaba calculando los hijos del nodo 7 y ya había llamado a CalculaNodos para su rama izquierda. Continuará entonces invocando de nuevo a CalculaNodos para su rama derecha, esperando el resultado correspondiente (el cual le llegará unas cuantas llamadas recursivas después). Sumará ambos resultados de cada rama y retornará el resultado a quien hizo llamada 1, que hará lo propio, etc.

Es decir, la gracia de las recursivas es que cuando retornan, no dan por terminado el problema, sino sólo el subproblema de que se estaban ocupando. Y ten en cuenta que el subproblema de contar los nodos de una rama no es diferente del problema final de contar los nodos de un árbol. La diferencia es tan sólo en qué nivel del árbol estás y a quién retornarás el resultado.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.