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.