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

[anonim]

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.

#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);
   }}

 

[Mark44]

    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.

 

[anonim]

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.

 

[Mark44]

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.

 

[anonim]

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!

 

[Mark44]

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$.

 

[Mark44]

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:

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.

 

[willem2]

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.

 

[anonim]

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:

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?

 

[Mark44]

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.

result = func(n - 1, r - 1);

 

[anonim]

The version I wrote does call itself. Look at the next-to-last line of code.

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

 

[Mark44]

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.

 

[Mark44]

@anonim, did you ever make any progress on this?