recursive combination function

Page 1 of 1

10 Replies - 2306 Views - Last Post: 03 October 2012 - 01:40 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=294117&amp;s=6fde017389c601c65136928384cce18f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 paul13

Reputation: 0
• Posts: 14
• Joined: 21-May 12

recursive combination function

Posted 03 October 2012 - 09:49 AM

i need to calculate combinations of n taken by k but i keep getting wrong results and di don't know where is the mistake

this is the function
```long comb(int n,int k)
{
if((n==k)||(k==0)||(n==0))
return 0;
if(k>0 && k<n)
return (comb((n-1),k)+comb((n-1),(k-1)));

}

```

and this is main
```	int m,n;
cin>>m;
cin>>n;
cout<<comb(m,n);
```

Is This A Good Question/Topic? 0

Replies To: recursive combination function

#2 jimblumberg

Reputation: 4647
• Posts: 14,572
• Joined: 25-December 09

Re: recursive combination function

Posted 03 October 2012 - 09:55 AM

What did you input in main()? What output do you receive? What output do you expect?

Jim

#3 paul13

Reputation: 0
• Posts: 14
• Joined: 21-May 12

Re: recursive combination function

Posted 03 October 2012 - 10:07 AM

http://www.calculato...ombinations.php

I get only zeros and weird numbers

#4 jimblumberg

Reputation: 4647
• Posts: 14,572
• Joined: 25-December 09

Re: recursive combination function

Posted 03 October 2012 - 10:13 AM

That link doesn't tell me anything.

What did you enter for the value of m?

The value of n?

What value do you expect to see with these inputs?

Jim

#5 paul13

Reputation: 0
• Posts: 14
• Joined: 21-May 12

Re: recursive combination function

Posted 03 October 2012 - 10:26 AM

i used the following recurssive formula c(n,k)=c(n-1,k)+c(n-1,k-1) for any k>0,K<n
i inputted m=9,n=4,the result was 0...it should have been 126

#6 Skydiver

• Code herder

Reputation: 4250
• Posts: 13,597
• Joined: 05-May 12

Re: recursive combination function

Posted 03 October 2012 - 10:32 AM

According to the link you sent, combination of 1 taken 1 at a time is 1, yet your code says that if n == k, return 0.

#7 paul13

Reputation: 0
• Posts: 14
• Joined: 21-May 12

Re: recursive combination function

Posted 03 October 2012 - 10:38 AM

thanks,it works now

sorry for double post but why did i got only 0's when i used return 1 and the corect numbers when i used return 1?

thanks,it works now,but why did i got only 0's when i used return 0 and the corect numbers when i used return 1?

#8 jimblumberg

Reputation: 4647
• Posts: 14,572
• Joined: 25-December 09

Re: recursive combination function

Posted 03 October 2012 - 10:38 AM

Also that link is using factorials:

Quote

C(9,4) = 9! / ( 4! (9 - 4)! ) = 126

Where are you computing the factorials?

Jim

#9 paul13

Reputation: 0
• Posts: 14
• Joined: 21-May 12

Re: recursive combination function

Posted 03 October 2012 - 10:40 AM

i used this recurssive formula c(n,k)=c(n-1,k)+c(n-1,k-1) that does the job

but still why didn't it work with return 0

#10 mojo666

Reputation: 382
• Posts: 827
• Joined: 27-June 09

Re: recursive combination function

Posted 03 October 2012 - 01:36 PM

Because your recursive calls keep breaking down until they match a base case. At that point they returned 0. You would only be adding 0's to each other.

For example, comb(2, 1) -> Return comb(1,1)+comb(1,0) -> 0+0

#11 Skydiver

• Code herder

Reputation: 4250
• Posts: 13,597
• Joined: 05-May 12

Re: recursive combination function

Posted 03 October 2012 - 01:40 PM

I recommend simulating what the computer is doing on paper or on the whiteboard. It becomes much clearer when you do it yourself versus somebody just showing you the callstack and the values of the variables. Gaining an understanding and good feel for recursion now will save you headaches down the road when you have to tackle data structures (like trees), or algorithms (like quicksort).

If the recursive combinations in a bit too hairy for you, start of with the recursive implementation of factorial: factorial(n) = n * factorial(n-1) where factorial(0) == 1.