10 Replies - 1641 Views - Last Post: 03 October 2012 - 01:40 PM Rate Topic: -----

#1 paul13  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • member icon


Reputation: 4278
  • View blog
  • Posts: 13,443
  • 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
Was This Post Helpful? 0
  • +
  • -

#3 paul13  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is offline

  • member icon


Reputation: 4278
  • View blog
  • Posts: 13,443
  • 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
Was This Post Helpful? 0
  • +
  • -

#5 paul13  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3662
  • View blog
  • Posts: 11,472
  • 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.
Was This Post Helpful? 0
  • +
  • -

#7 paul13  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#8 jimblumberg  Icon User is offline

  • member icon


Reputation: 4278
  • View blog
  • Posts: 13,443
  • 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
Was This Post Helpful? 0
  • +
  • -

#9 paul13  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#10 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 356
  • View blog
  • Posts: 785
  • 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
Was This Post Helpful? 0
  • +
  • -

#11 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3662
  • View blog
  • Posts: 11,472
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1