# need help with c++ recursion

Discussion in 'OT Technology' started by hurleyint1386, Apr 14, 2005.

1. ### hurleyint1386Someone has sand in their vagina

Joined:
Jan 6, 2005
Messages:
3,687
0
Location:
Rochester, NY
ok, i have this small lab that i need to do, and it seems fairly simple, but i cant get it. i think i need to use loops in my function, but im not sure. here's the problem:

Forming Committees.
Let comm(n, k) represent the number of different committees of k people that can be formed if you have n people available. For example, comm(4, 3) = 4, since of four people, A, B, C, and D, there are four possible three-person committees: ABC, ABD, ACD, and BCD. In general, comm(n, k) = comm(n-1, k) + comm(n-1, k-1). Write and test arecursive C++ function to compute comm(n, k) for n>=1, k>=1.

that's the problem, and i know how to do it in my head, but i can't think of how to put it into code. can anyone help me?

2. ### hurleyint1386Someone has sand in their vagina

Joined:
Jan 6, 2005
Messages:
3,687
0
Location:
Rochester, NY
*bump*
anyone?

3. ### skinjobActive Member

Joined:
Jan 6, 2001
Messages:
2,337
0
Location:
Aztlán
In any recursive algorithm, ask yourself what the base case or cases are.
In your problem, I think there are 3 base cases you need to handle.
1) what do you return if n == k?
2) what do you return if k == 1?
3) what do you return if k > n?
If you arguments don't match any of the base cases, just call the function recursively.

4. ### hurleyint1386Someone has sand in their vagina

Joined:
Jan 6, 2005
Messages:
3,687
0
Location:
Rochester, NY
ok, that makes sense. i understand that part now. what would be the parameters of the function when it's called recursively? would it be comm(n-1, k) or is there more to it than that?

5. ### skinjobActive Member

Joined:
Jan 6, 2001
Messages:
2,337
0
Location:
Aztlán

comm(n-1, k) + comm(n-1, k-1)

It's not really a single recursive call.

6. ### hurleyint1386Someone has sand in their vagina

Joined:
Jan 6, 2005
Messages:
3,687
0
Location:
Rochester, NY
so how do i do a double recursive call? i dont remember my teacher mentioning how it, unless i didnt notice. would it be something like:

comm(n-1, k);
comm(n-1, k-1);

because i has to be more than that.

7. ### skinjobActive Member

Joined:
Jan 6, 2001
Messages:
2,337
0
Location:
Aztlán
Code:
```
int comm(int n, int k)

{[indent]if (parameters match a base case)

{[indent]return ???;

[/indent]}

// otherwise...
return comm(n-1, k) + comm(n-1, k-1);

[/indent]}```

8. ### hurleyint1386Someone has sand in their vagina

Joined:
Jan 6, 2005
Messages:
3,687
0
Location:
Rochester, NY
i tried this, and it's compiling, however it's not giving me correct answers. if k == n, it doesnt give me 1, but if k > n, then it returns 0 correctly ....

9. ### skinjobActive Member

Joined:
Jan 6, 2001
Messages:
2,337
0
Location:
Aztlán
It works for me. Check your input values.

10. ### hurleyint1386Someone has sand in their vagina

Joined:
Jan 6, 2005
Messages:
3,687
0
Location:
Rochester, NY
here's my main function. maybe there's something wrong with it for me. above my main ive got a
"int numberofcommittees(int n, int k);" prototype.

it's probably something so stupid that im over looking. does this work for you?

11. ### hurleyint1386Someone has sand in their vagina

Joined:
Jan 6, 2005
Messages:
3,687
0
Location:
Rochester, NY
bump

almost finished, just a few problems

12. ### hurleyint1386Someone has sand in their vagina

Joined:
Jan 6, 2005
Messages:
3,687
0
Location:
Rochester, NY
i still need some help. can anyone help me finish? im not sure why it's giving me incorrect answers

13. ### skinjobActive Member

Joined:
Jan 6, 2001
Messages:
2,337
0
Location:
Aztlán
I did a copy & paste of your code. It compiles and works fine for me.
Post a sample of the input and output you're seeing.

14. ### hurleyint1386Someone has sand in their vagina

Joined:
Jan 6, 2005
Messages:
3,687
0
Location:
Rochester, NY
here's the program, the first time, i tried 3 people in a committee with 4 people, and the answer should be 4. then i tried doing 3 people to a committee with 3 people, which should be 1, but it says 3

15. ### skinjobActive Member

Joined:
Jan 6, 2001
Messages:
2,337
0
Location:
Aztlán
Carefully compare your code with what you posted.
Make sure they are the same.
Maybe even wipe out what you have and just copy and paste from this thread.
It works for me.

Joined:
Jan 6, 2005
Messages:
3,687