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

  • Comp Sci
  • Thread starter anonim
  • Start date
  • Tags
    Recursion
In summary, the code 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",
  • #1
anonim
40
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);
   }}
 
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes berkeman
  • #3
Mark44 said:
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
anonim said:
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
Mark44 said:
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
anonim said:
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
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
Mark44 said:
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
Mark44 said:
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
anonim said:
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
Mark44 said:
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
anonim said:
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.
 
  • Like
Likes sysprog
  • #13
@anonim, did you ever make any progress on this?
 

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

1. What is recursion and how does it work?

Recursion is a programming technique where a function calls itself repeatedly until a certain condition is met. This allows for solving complex problems by breaking them down into smaller, simpler versions of the same problem.

2. How can recursion be used to calculate (n + r)/(n * r)?

To calculate (n + r)/(n * r) using recursion, we can break down the problem into smaller parts by repeatedly subtracting 1 from n and r until they reach 0. Then, we can use the base case of n or r being 0 to return the final result.

3. What are the advantages of using recursion to solve this problem?

One advantage of using recursion is that it allows for a more elegant and concise solution to complex problems. It also helps in reducing the time and space complexity of the program by breaking down the problem into smaller parts.

4. Are there any limitations to using recursion?

Yes, there are some limitations to using recursion. One limitation is that it can lead to stack overflow if the recursive function is called too many times without reaching the base case. It also requires more memory as the function calls are stored on the call stack.

5. How can we optimize the recursive solution for calculating (n + r)/(n * r)?

To optimize the recursive solution, we can use memoization, where we store the results of previously calculated values in a data structure and retrieve them instead of recalculating. This can help in reducing the time complexity of the program.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
19
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
4
Views
962
  • Engineering and Comp Sci Homework Help
Replies
3
Views
692
  • Engineering and Comp Sci Homework Help
Replies
17
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
12
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
915
  • Engineering and Comp Sci Homework Help
Replies
1
Views
8K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
774
  • Engineering and Comp Sci Homework Help
Replies
17
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
18
Views
1K
Back
Top