C语言递归实现卡特兰数计算代码问题求助

安全阿岳

2026-10-2

问题根因

你的代码核心问题是整数运算顺序错误，C语言中整数除法会直接截断小数部分，你当前的实现先执行除法再执行乘法，会导致中间结果截断产生误差，举个实际例子：

计算n=3的卡特兰数时，原代码先计算 (2*(2*3-1))/(3+1) = 10/4 = 2（整数截断），再乘以C(2)=2，得到错误结果4；而正确计算顺序应该是先乘后除：2*(2*3-1)*C(2) = 10*2=20，再除以4得到正确结果5。
此外当n取值增大时，int类型的取值范围不足以存储卡特兰数，建议替换为更大范围的整数类型。

修改后的代码

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

// 改用long long避免溢出，调整运算顺序为先乘后除
long long catalanRecursief(int n) {
    if (n == 0){
        return 1;
    } else { 
        return (2 * (2 * n - 1) * catalanRecursief(n - 1)) / (n + 1);
    }
}

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

    printf("Catalan number: %d > %lld", n, catalanRecursief(n));
    
    getchar();
    getchar(); // 额外加一个getchar抵消scanf留下的换行符，避免运行窗口一闪而过
    return 0;
}