I'm struggling with some code I have to write for an assignment in C. I have to calculate a Catalan number recursively. The following formula is given: Formula IMG.

The awnsers should be:

0 > 1 (Filling in 0 should print 1)

5 > 42 (Filling in 5 should print 42)

7 > 429 (Filling in 7 should print 429)

9 > 4862 (Filling in 9 should print 4862)

10 > 16796 (Filling in 10 should print 16796)

Please have a look at it:

#pragma warning(disable : 4996)
#include <stdio.h>

int catalanRecursief(int n) {
    if (n == 0){
        return 1;
    } else { 
        return (2 * ((2 * n) - 1)) / (n   1) * (catalanRecursief(n - 1));
}
}


int main(void){
    int n;
    printf("Catalan printer\n\n");
    printf("What catalan number do you want to calculate? ");
    scanf("%d", &n);

    /*catalanRecursief(n);*/

    printf("Catalan number: %d > %d", n, catalanRecursief(n));
    
    getchar();
    return(0);
    
}

CodePudding user response：

By changing the unit from n to float it will be enough to solve it.

int catalanRecursief(float n) {
  if (n == 0) {
    return 1;
  } else {
    return ((2 * ((2 * n) - 1)) / (n   1)) * (catalanRecursief(n - 1));
  }
}

or also

int catalanRecursief(int n) {
  if (n == 0) {
    return 1;
  } else {
    return ((2.0 * ((2 * n) - 1)) / (n   1)) * (catalanRecursief(n - 1));
  }
}

this is because dividing int numbers c truncates them

CodePudding user response：

As the theory says that Catalan numbers are integers, you should just ensure that the division happens last to avoid an integer division truncation:

...
else {
    return (2 * ((2 * n) - 1)) * (catalanRecursief(n - 1)) / (n   1);
}
...

With 32 bits integers, overflow is to be expected starting at C₁₇, so use long long if you want to go further...