Thread: Really hard recursion with boxes, help?

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    29

    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);
             }
    }
    Last edited by aciarlillo; 10-12-2005 at 02:17 PM.

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    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?

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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 . . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Extracting data from a laptop hard drive
    By DavidP in forum Tech Board
    Replies: 6
    Last Post: 06-13-2009, 07:02 AM
  2. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  3. Detect SCSI Hard Drive Serial Number
    By mercury529 in forum Windows Programming
    Replies: 3
    Last Post: 10-17-2006, 06:23 PM
  4. Replies: 2
    Last Post: 07-06-2005, 07:11 PM
  5. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM