Sign in to follow this  

recursive function check

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Conner McCloud
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


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

Share this post


Link to post
Share on other sites
Quote:
Original post by nilkn
That 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 this post


Link to post
Share on other sites
Quote:
Original post by Andorien
From 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.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this