Public Group

# recursive function check

This topic is 4494 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Can anyone look at my function. I haven't used recursion much and just want to know if I did this right. It's supposed to count the number of possible seat combinations given n. where n is the number of people and seats.
int count = 0;

void test( int n )
{
// we know that when there are only 2 seats/people
// there are 2 combinations so add those to count
if ( n == 2 )
{
count += 2;
return;
}

for ( int i = 0; i < n; i++ )
{
test(n-1);
}
}



##### Share on other sites
For starters you will be required to create a prototype of the function or you will get a compile time error. I am unsure about whether your algorithm is correct because I do not understand it. That function will however recurse successfully.

##### Share on other sites
That doesn't look right to me. Perhaps try something like this:

int CountCombinations(const int n){     if (n <= 2)          return n;     else          return n*CountCombinations(n-1);}

It assumes n >= 0.

##### Share on other sites
Eew eew eew. Get rid of that global variable, right now.

Call that function twice in a row, and you get a wrong answer the second time. That's bad.

CM

##### Share on other sites
Well, I'm gonna try to break it down for anyone that cares...

Basically you call test with how many people you have. So if you have 3 people call test(3) to see how many combinations you can seat them in.

So if you have a row of 3 seats the people can be seated in any of these combinations (i think this is right):

123
132

213
312

321
231

So from what I understand you are supposed to break the problem down into a simpler problem that you can answer easily. So I knew that if I had 2 people/seats that I could only put them in 2 different combinations:

12
21

The for loop just moves the first person to each seat and then breaks it down to one less person/seat to test until it gets to 2. So here the first person starts in seat 1 and then we call test(n-1), now n==2 so I add 2 to count for the two combinations (above: 123 and 132). Now we the for loop moves the first person to seat 2 and we call test(n-1), again n==2 so I add 2 for the 2 combinations(213 and 312). Loop again and the first person is in seat 3 and we call test(n-1), n==2 so we add 2 again for the combinations (321 and 231). There's no where else for the first person to move so we are done.

We found 6 possible seating combinations. Hopefully you can see how it works for more than 3 people cause that would probably cause my brain to explode to try and break that down :P

I hope that explains what I'm doing better. This stuff is hard to explain. It was hard enough coming up with something that worked... lol :P

##### Share on other sites
Quote:
 Original post by Conner McCloudEew eew eew. Get rid of that global variable, right now.Call that function twice in a row, and you get a wrong answer the second time. That's bad.CM

lol yea i know i shouldnt use that i just threw this together quick to see what would come up.

##### Share on other sites
Quote:
 Original post by nilknThat doesn't look right to me. Perhaps try something like this:*** Source Snippet Removed ***It assumes n >= 0.

I knew there had to be an easier way. That looks much better. Thanks. I'm thinking too much about it I think.

##### Share on other sites
Edit: now I see someone did it faster and better :P

##### Share on other sites
Quote:
 Original post by AndorienFrom what I can see, you don't actually have a way to retrieve the result. You'd need something like this*** Source Snippet Removed ***I think that should do it.

I tried that at first too but that return in the loop means it will only loop once so the answer doesn't come out right. nilkn did it right, I just wasn't thinking to multiply instead of doing the loop.

1. 1
Rutin
24
2. 2
3. 3
JoeJ
18
4. 4
5. 5

• 38
• 23
• 13
• 13
• 17
• ### Forum Statistics

• Total Topics
631708
• Total Posts
3001841
×