I have a recursive function that calculates the number of nodes that a binary tree has, obviously it works fine, but there is one thing I don't understand.
#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;
}
It goes in preorder, you know, root first, then visit left child, then right child. The question is that when I have been doing it, if for example we have this tree:
What it does is:
- It checks that the tree is not empty, so in the first function, it goes to the else directly since the tree is rooted.
- The recursion begins, the root, the tree and the counter are passed to 1 (since it has at least 1 node, which is the root).
- We start the second function, since it has a left child that is 7 and it is not a null node, it calls calculateNodos again with node 7, the tree, and the counter at 2 (we already have 1 root node, and 1 node that is 7 , in total, 2 nodes).
- It is called recursively again, and it turns out that it has a left child, which is 2 and is not a null node, again we call calculateNodes with node 2, the tree, and the counter at 3 (total 3 nodes, root, 7 and 2).
HERE COMES MY DOUBT:
5. It is called recursively again and now node 2 has neither left nor right child, that is, in calculateNodes, it skips the first if and the second if, and returns counter.
My question is, running the program works perfectly for me, but what I don't understand is how if it returns the counter there, the program continues counting the right child of 7, which would be 6, but if it has already returned the counter... That is, How does the recursion work there so that it continues reading the right child of 7 (which is 6) if it has already returned counter and finished.
Thank you very much.
Note that when you make a recursive call, you are actually calling another function (although in this particular case the function you are calling is the same one). The function that made the call will be resumed later, when the function you called returns.
Thus, the first time you call
CalculaNodos
fromnumNodos
passing the root (node 2), the latter will wait for it toCalculaNodos
finish and return its result. Let's call this first call call 0 .But
CalculaNodos
, in turn callsCalculaNodos
passing it node 7, and waits for its result. Let's call this second call call 1.It
CalculaNodos
calls againCalculaNodos
( call 2 ) passing it node 2, and waits for the result.Here we finally come to a call that doesn't make any more recursive calls. This last call returns 3 as you calculated, but who does that 3 return to? Who made the call 2 . So we are back inside the function
CalculaNodos
when it was calculating the children of node 7 and had already called aCalculaNodos
for its left branch. It will then continue calling a againCalculaNodos
for its right branch, waiting for the corresponding result (which will arrive a few recursive calls later). It will add both results of each branch and return the result to the caller 1 , who will do the same, etc.That is, the grace of recursive is that when they return, they do not consider the problem finished, but only the sub -problem they were dealing with. And note that the subproblem of counting the nodes of a branch is no different from the final problem of counting the nodes of a tree. The difference is just what level of the tree you are at and to whom you will return the result.