Really hard recursion with boxes, help?

The problem is to use recursion to count how many boxes are in a room. The trick is each box can have boxes inside of it and each one of those can have even more inside of it. It is supposed to begin by asking "How many unnumbered boxes do you see? " you input the number. Then for each of these it asks how many you see inside i.e. (How many do you see in box #1?" Then for each of the ones inside it will ask "How many do you see inside 1.1? .... 1.2? .... 1.3" and so on. I have tried my best at this but I think it is just outside my understanding of recursion so far, especially keeping track of 1.1 1.2 1.1.1 1.2.1 etc etc. I have some code posted below that can so far count the number of boxes within 1 box but thats as far as I can go. We are allowed to use functions but I do not see where this will help. Any suggestions or pushes in the right direction would be appreciated.
Thanks
-a

Code:

---

int find_boxes(int a, int& t, int pre);
void count_boxes(int n);
int boxes;
int main()
{
    int a;
    char c;
   
    cout << "How many unnumbered boxes do you see? - " ;
    cin >> a;
    boxes = a;
    count_boxes(a);
    cout<< "There are: " << boxes << " boxes in the room.\n";
    cin >> c;
         
}

int find_boxes (int ans, int& total, int pre){
    int x;
    if(ans == 0)
            return total;
    while (ans != 0){ 
          cout << "How many do you see in box " << pre << "." << ans << ": ";
          cin >> x;
          total += x;
          return find_boxes(x, total, pre+1);
          ans --;
          }
    return total;
}

void count_boxes(int n){
    for ( int i = 1; i <= n; i++){
        find_boxes(n-i, boxes, i);
        }
}

---

I don't think you should be using ans == 0 as the condition to end the recursion. Logically, doesn't the recursion end when the user says there are 0 boxes inside the current box?

A small disreprency:

Code:

---

int find_boxes(int a, int& t, int pre);
// ...
int find_boxes (int ans, int& total, int pre){

---

You might want a stack . . . starting with box 1, you push '1' onto the stack. Then you push '1', and another '1', and another . . . .

The first thing to understand is that recursion is a hard thing to visualise if you have never encountered it before.

One comparison is the nested "for loop".

For example:

Code:

---

for (int a=0; a<=1; a++)
{
  for(int b=0; b<=5; b++)
  {
    cout<<a<<" "<<b<<endl;
    }
}

---

As you can see, one for loop is 'nested' within the other.

Sample run:

Code:

---

a b
----
0 0
0 1
0 2
0 3
0 4
0 5
1 0
1 1
1 2
1 3
1 4
1 5

---

So basically before 'a' can increment from zero to one it has to loop through 'b' from zero to five first. It is important to understand the way this operates since this is how your recursive function will work- in much the same way.

Ok, so how does that help with your problem?
Well the best way to approach this would be to draw a sample diagram. (A picture is worth a thousand words) A tree diagram serves as the best example.

In the diagram below, let each folder be representative of a box.
The question is how would we recursively search all the boxes?

Well, think back to the nested for loop and remember this rule:-

"As soon as you encounter another level of nesting you immediately, search that level. Once you have finished searching that entire level you go back to the preceding level."

Ok so given that rule, how might we search the boxes in the diagram below?

Code:

---

how many boxes in the room>>2

how many in box 1>> 2

how many in box 1.1>> 0

how many in box 1.2>>1

how many in box 1.2.1>>0

how many in box 2>> 0

End program

---

That would be how. Notice that before box 2 is searched all the sub-folders of box 1 has to be searched first.

Ok so how would you put that into code?

Code:

---

/*-----------------------------------------------------------
 
    A problem with recursion:
 -----------------------------------------------------------*/
 
 #include <iostream>
 
 void find_boxes(int);
 
 using namespace std;
 
 int main()
 {
    cout<<"How many boxes do you see in the room\n>>";
    int x;
    cin>>x;
   
    find_boxes(x);
    cin.get();
    cin.get();
 }
 
 /*------------------------------
 recursive function: find boxes
 -------------------------------*/
 void  find_boxes(int x)
 {
    for (int i=1; i<=x; i++)
    {
      cout<<"How many boxes are in box "<<i<<endl;
      int y;
      cin>>y;
       
        if (y!=0)
        { 
          find_boxes(y);
          //move to next box
        }
        else if(y==0)
        {
            //move to preceeding box
        }   
           
    } 
   
 }

---

I have no intention of doing your homework for you. The program is not complete. You have to think of a way to make it display the numbers for the boxes properly. For example, box 1.2.1. Other than that the code behaves as expected.

One other thing, notice that you don't need to 'return' anything to main. You simply pass the variable back into the recursive function. I hope this helps.

Ps. An example of a tree diagram can be found if you go to the 'command prompt' and type tree.