Using Recursion to Calculate (n + r)!/(n! * r!)

  • Comp Sci
  • Thread starter anonim
  • Start date
  • #1
anonim
39
2
Homework Statement:
Calculate math formula
Relevant Equations:
(n+r)!/(n!.r!)
I wirte code but it does not work. I entered n=5 and r=2, result is 0. And I want to calculate this recursively.
Code:
#include<stdio.h>
int func(int n, int r);
int main(){
    int n,r;
    int result=0;
    printf("Enter the number:\n");
    scanf("%d",&n);
    printf("Enter the 2.number:\n");
    scanf("%d",&r);
  
   result=func(n,r);
   printf("%d",result);
  
    return(0);
}
int func(int n, int r){
    if(r==1){
        return(n);
    }
   if(n>0 && r>0){
       return ((n+r) / (n*r))* func(n-1,r-1);
   }


}
 

Answers and Replies

  • #2
36,708
8,701
anonim said:
C:
    return ((n+r) / (n*r))* func(n-1,r-1);
For one thing this isn't the right formula.

$$\frac {(n + r)!}{n! \cdot r!} = \frac{n + r}{n \cdot r} \frac{(n + r - 1)!}{(n - 1)!(r - 1)!}$$

Your code might have other problems, but this is the first thing that jumped out at me.
 
  • #3
anonim
39
2
For one thing this isn't the right formula.

$$\frac {(n + r)!}{n! \cdot r!} = \frac{n + r}{n \cdot r} \frac{(n + r - 1)!}{(n - 1)!(r - 1)!}$$

Your code might have other problems, but this is the first thing that jumped out at me.
Yes, you are right. It also doesn't return the true result of the division. For example if 5/6 it returns 0. But I have to write int function.
 
  • #4
36,708
8,701
Yes, you are right. It also doesn't return the true result of the division. For example if 5/6 it returns 0. But I have to write int function.
It shouldn't return a fraction such as 5/6. The result should only be an integer. What you're trying to calculate is the number of combinations of ##n + r## things taken ##r## at a time. This is defined as
$$\frac{(n + r)!}{n! \cdot r!}$$.

For example, the number of combinations of 5 things taken 2 at a time is ##\frac{5!}{(5 - 2)! \cdot 2!} = \frac{5!}{3! \cdot 2!} = 10##. These combinations always come out with integer values of at least 1.
 
  • #5
anonim
39
2
It shouldn't return a fraction such as 5/6. The result should only be an integer. What you're trying to calculate is the number of combinations of ##n + r## things taken ##r## at a time. This is defined as
$$\frac{(n + r)!}{n! \cdot r!}$$.

For example, the number of combinations of 5 things taken 2 at a time is ##\frac{5!}{(5 - 2)! \cdot 2!} = \frac{5!}{3! \cdot 2!} = 10##. These combinations always come out with integer values of at least 1.
Okay if n=5 and r=5--> 10!/5!*5! is not equal 5!/0!*5!
 
  • #6
36,708
8,701
Okay if n=5 and r=5--> 10!/5!*5! is not equal 5!/0!*5!
First off, please use parentheses when they are needed.
10!/5!*5! means ##\frac {10!}{5!} \cdot 5!##, which I don't think is what you meant.
If you don't use LaTeX, write it as 10!/(5! * 5!).
Second, ##\frac {10!}{5! 5!} = \binom {10} 5##, which is the number of combinations of 10 things taken 5 at a time, and is equal to 36. This is sometimes written as ##_{10}C^5##.
 
  • #7
36,708
8,701
anonym said:
C:
int func(int n, int r){
    if(r==1){
        return(n);
    }
   if(n>0 && r>0){
       return ((n+r) / (n*r))* func(n-1,r-1);
   }
}
I was able to write some code that seems to work, but I changed the meaning of the two parameters. In your function you are using n and r to mean the number of combinations of (n + r) things taken n at a time, and this is defined as
$$\frac{(n + r)!}{n! \cdot r!}$$
By symmetry, this is exactly the same as (n + r) things taken r at a time.

In my code, I'm looking that the number of combinations of N things taken k and a time, or
$$\frac {N!}{(N - k)! \cdot k!}$$
My N is your n + r, and my N - k is your r.

One thing I found is that if you do the division too soon, the integer division produces incorrect results. To counter this, I added an extra line.

In your code, which I believe uses an incorrect formula, the change would look like this:
C:
int func(int n, int r){
    int result;
    if(r==1){
        return(n);
    }
   if(n>0 && r>0){
       result = func(n - 1, r - 1);
       return result * (n + r) / (n * r);
   }
}
If you save the division for last, you won't have the problem of your code evaluating something like 5/6, resulting in a value of 0.

Again, though, your formula is wrong and still needs to be fixed.
 
  • #8
willem2
2,103
365
Again, though, your formula is wrong and still needs to be fixed.
Yes. Compare the numerators wit both (n,r) and (n-1, r-1)

It might be easier to calculate func(n, r) from func (n, r-1). Less calculations for each step, and the same number of steps.
 
  • #9
anonim
39
2
I was able to write some code that seems to work, but I changed the meaning of the two parameters. In your function you are using n and r to mean the number of combinations of (n + r) things taken n at a time, and this is defined as
$$\frac{(n + r)!}{n! \cdot r!}$$
By symmetry, this is exactly the same as (n + r) things taken r at a time.

In my code, I'm looking that the number of combinations of N things taken k and a time, or
$$\frac {N!}{(N - k)! \cdot k!}$$
My N is your n + r, and my N - k is your r.

One thing I found is that if you do the division too soon, the integer division produces incorrect results. To counter this, I added an extra line.

In your code, which I believe uses an incorrect formula, the change would look like this:
C:
int func(int n, int r){
    int result;
    if(r==1){
        return(n);
    }
   if(n>0 && r>0){
       result = func(n - 1, r - 1);
       return result * (n + r) / (n * r);
   }
}
If you save the division for last, you won't have the problem of your code evaluating something like 5/6, resulting in a value of 0.

Again, though, your formula is wrong and still needs to be fixed.
Shouldn't function constantly call itself? Is this still recursion?
 
  • #10
36,708
8,701
Shouldn't function constantly call itself? Is this still recursion?
The version I wrote does call itself. Look at the next-to-last line of code.
C:
result = func(n - 1, r - 1);
 
  • #11
anonim
39
2
The version I wrote does call itself. Look at the next-to-last line of code.
C:
result = func(n - 1, r - 1);
Yes, right. But it doesn't work if I entered 5 and 2 , output-2. But if n-5 and r-5 ->output-21
 
  • #12
36,708
8,701
Yes, right. But it doesn't work if I entered 5 and 2 , output-2. But if n-5 and r-5 ->output-21
Like I said before, your formula is incorrect.
In my code, which I haven't shown, entering 5 and 2 gives 10, which is the correct result for the number of combinations of 5 things taken 2 at a time.

In your code, if n = 5 and r = 2, then you should be getting the number of combinations of 7 things (5 + 2) taken 2 at a time, which is 21.

In post #2, I pointed out what was wrong with your code.
 
  • #13
36,708
8,701
@anonim, did you ever make any progress on this?
 

Suggested for: Using Recursion to Calculate (n + r)!/(n! * r!)

  • Last Post
Replies
11
Views
241
Replies
4
Views
916
Replies
2
Views
219
  • Last Post
Replies
1
Views
293
Replies
8
Views
619
  • Last Post
Replies
4
Views
678
Replies
19
Views
1K
Replies
3
Views
3K
Top