Evaluating binomial coefficients

vasiqshair (51)
This function should evaluate the binomial cofficient C(4,2) = 6. Instead, it is giving me a runtime error. Recursion is hard to understand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <iostream>
using namespace std;

int recursivebinomial(int, int);
int main()
{
	int m = 4;
	int n = 2;
	cout << "Evaluating the binomial coefficients" << endl;
	int h = recursivebinomial(m,n);
	cout << h << endl;
	return 0;
}
int recursivebinomial(int m, int n)
{
	if(m != 0 && n == 0)
		return 1;
	else if(m == 0 && n != 0)
		return 0;
	else
		return recursivebinomial(--m, --n) + recursivebinomial(--m, n);
}
kev82 (323)
Mathematically, what recursive formula are you using?

What you appear to have implemented there is C(n,k) = C(n-1,k-1)+C(n-2,k-1). I'm not convinced that is correct.
Last edited on
vasiqshair (51)
kev82, i am not sure what you are referring to. Is my program incorrect or the formula that I am using? Because the error is a runtime. Anyways, I figured out what was wrong, and here is the correct code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <iostream>
using namespace std;

int recursivebinomial(int, int);
int main()
{
	int m = 4;
	int n = 2;
	cout << "Evaluating the binomial coefficients" << endl;
	int h = recursivebinomial(m,n);
	cout << h << endl;
	return 0;
}
int recursivebinomial(int m, int n)
{
	if(n == 0)
		return 1;
	else if(m == 0)
		return 0;
	else
		return recursivebinomial(--m, --n) + recursivebinomial(m, n + 1);
}
helios (17607)
You're causing undefined behavior by using [a variable you're decrementing] twice in the same expression.
Change line 21 to this:
return recursivebinomial(m-1, n-1) + recursivebinomial(m-1, n);
kev82 (323)
You were using the wrong formula, and not catching all the base cases of it. By inserting a print statement you can watch yourself go beyond 0,0 towards the inevitable stack overflow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
C(4,2)
C(3,1)
C(2,0)
C(1,0)
C(2,1)
C(1,0)
C(0,0)
C(-1,-1)
C(-2,-2)
C(-3,-3)
C(-4,-4)
C(-5,-5)
C(-6,-6)
C(-7,-7)


@helios

Is that undefined? Doesn't precedence give that a clear definition?
helios (17607)
No. Save for a few exceptions (the rule is rather complicated and not too important), any expression where a {pre|post}{in|de}crement is applied to x and x appears again in the same expression, has undefined behavior.
Topic archived. No new replies allowed.