C语言：实现判断无符号长整数不同奇数位数的递归函数问题

嘿，我来帮你搞定这个递归函数的问题！你现在的核心痛点是没法跟踪哪些奇数已经出现过，对吧？因为不能用全局/静态变量，那我们就得想办法把“已出现的奇数”这个状态通过递归参数传递出去——但函数签名只有一个参数，怎么办？我们可以把这个状态编码到参数的二进制位里，毕竟unsigned long有足够多的位可以用~

思路核心 #

奇数数字只有1、3、5、7、9这5个，刚好可以用5个二进制位来标记它们是否出现过：

• 第0位（最低位）标记1是否出现
• 第1位标记3是否出现
• 第2位标记5是否出现
• 第3位标记7是否出现
• 第4位标记9是否出现

我们把unsigned long参数拆成两部分：

• 高5位：存储上述的标记（mask）
• 低59位：存储当前需要处理的数字n

初始调用时，用户传入的n的高5位都是0（因为n是正自然数，不会用到这么高位），所以mask初始为0，我们直接处理低59位的n即可。

完整代码实现 #

int check_odd(unsigned long param) {
    // 拆分出当前要处理的数字和已出现奇数的标记
    unsigned long current_n = param & ((1ULL << 59) - 1);
    int mask = param >> 59;

    // 递归终止条件：所有数字处理完毕
    if (current_n == 0) {
        // 统计标记中1的个数（即不同奇数的数量）
        int count = 0;
        for (int i = 0; i < 5; i++) {
            if (mask & (1 << i)) {
                count++;
            }
        }
        // 判断数量是否小于3，是则返回1，否则返回0
        return count < 3 ? 1 : 0;
    }

    // 取当前数字的最后一位
    int digit = current_n % 10;
    int new_mask = mask;

    // 如果是奇数，更新标记
    if (digit % 2 == 1) {
        int bit_pos;
        // 映射奇数到对应的标记位
        switch (digit) {
            case 1: bit_pos = 0; break;
            case 3: bit_pos = 1; break;
            case 5: bit_pos = 2; break;
            case 7: bit_pos = 3; break;
            case 9: bit_pos = 4; break;
            default: bit_pos = -1; // 不可能走到这里
        }
        // 如果该奇数还没出现过，就把对应位设为1
        if (!(new_mask & (1 << bit_pos))) {
            new_mask |= (1 << bit_pos);
        }
    }

    // 构建新的参数：把处理后的数字（current_n/10）和新标记组合起来
    unsigned long new_param = (current_n / 10) | ((unsigned long)new_mask << 59);

    // 递归处理剩下的数字
    return check_odd(new_param);
}

代码解释 #

1. 参数拆分：用(1ULL << 59) - 1生成低59位的掩码，和param按位与得到当前要处理的current_n；把param右移59位得到当前的标记mask。
2. 终止条件：当current_n为0时，说明所有数字都处理完了，统计mask中1的个数，判断是否小于3并返回结果。
3. 处理当前位：取最后一位数字，如果是奇数，找到对应的标记位，若该位未被设置则更新标记。
4. 递归调用：把处理后的数字（去掉最后一位）和新标记重新组合成参数，继续递归。

测试你的示例 #

• check_odd(2169876)：数字中的奇数是1、9、7，对应标记位0、4、3被设置，count=3，返回0，符合要求。
• check_odd(956908529)：数字中的奇数是9、5，对应标记位4、2被设置，count=2，返回1，符合要求。

这样既满足了递归要求，又没有使用任何额外函数或全局/静态变量，完美解决你的问题！

内容的提问来源于stack exchange，提问作者Daniel Beck Bachar