递归实现C语言程序判断整数是否为4的倍数：问题排查

需求明确：

• 编写C程序，通过命令行接收参数n（字符串格式），转换为整数后判断是否为4的倍数
• 必须用递归实现，禁止使用取模运算符%，通过减法完成判断
• 若为4的倍数，输出格式必须为"4*i=n"；否则输出"!p4"

我尝试了多个版本的代码，但均存在问题：

1. 初始版本测试n=12时，错误判定为非4的倍数
2. 更新版本后问题仍未解决
3. 修改递归算法后，出现argc!=2恒成立、程序始终返回1的错误

初始版本代码 #

#include <stdio.h>
#include <stdlib.h>

void power4(int n, int i) {
    if (n < 0 || n == 1) {
        printf("!p4"); 
        return; 
    } 
    if (n == 0) {
        printf("4*");
        printf("%d", i);
        printf("=%d", n); 
    }
    power4(n - 4, i + 1); 

}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        return 1; 
    }
    int ptr = 0; 
    int* p = &ptr; 
    int c = strtol(argv[1], p, 10); 
    if (p == NULL) {
        return 1; 
    }
    power4(c, 1); 
    return 0; 
} 

更新后版本代码 #

#include <stdio.h>
#include <stdlib.h>

void power4(int n, int i) {
    if (n < 0 || n == 1) {
        printf("!p4"); 
        return; 
    } 
    if (n == 0) {
        printf("4*");
        printf("%d", i);
        printf("=%d", n); 
        return; 
    }
    power4(n - 4, i + 1); 
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        return 1; 
    }
    int c = strtol(argv[1], NULL, 10); 
    power4(c, 1); 
    return 0; 
}

修改递归算法后的版本代码 #

#include <stdio.h>
#include <stdlib.h>
void power4(int n1, int i, int n2) {
    // base case
    if (n1 % 4 != 0 && n1 != 1) {
        printf("!p4"); 
        return; 
}
    if (n1 == 1) {
        printf("4^%d=%d", i, n2); 
        return; 
    }
    // inductive step
    power4(n1 / 4, i + 1, n2); 
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        return 1; 
    }
    int c = strtol(argv[1], NULL, 10); 
    power4(c, 0, c); 
    return 0; 
}

问题分析与修正方案 #

1. 前两个版本的核心错误

• 递归基例缺失：仅处理了n==1的情况，但非4倍数的数减4后可能得到2、3等小于4的正数，这些情况未被拦截，会继续递归到n<0触发!p4；另外n==0时输出的是0而非原始输入的n，不符合格式要求。
• strtol用法错误：初始版本中第二个参数应为char**类型（用于接收转换后剩余字符的指针），而非int*，类型不匹配会引发未定义行为。

2. 第三个版本的错误

• 违反了禁止使用取模运算符的要求，且递归逻辑偏离需求（判断是否为4的幂而非4的倍数），输出格式也错误写成4^i=n，完全不符合要求。

正确实现代码

#include <stdio.h>
#include <stdlib.h>

// 递归判断是否为4的倍数，传入原始数值保证输出正确
void power4(int n, int original_n, int i) {
    // 基例1：n减到0，说明是4的倍数
    if (n == 0) {
        printf("4*%d=%d\n", i, original_n);
        return;
    }
    // 基例2：n小于4且不为0，说明不是4的倍数
    if (n < 4 && n != 0) {
        printf("!p4\n");
        return;
    }
    // 归纳步骤：每次减4，计数i加1
    power4(n - 4, original_n, i + 1);
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        return 1;
    }

    char* endptr;
    long num = strtol(argv[1], &endptr, 10);
    // 校验输入有效性：确保完全转换为整数且为正
    if (*endptr != '\0' || num <= 0) {
        return 1;
    }

    power4((int)num, (int)num, 0);
    return 0;
}

正确实现的关键点

• 递归时传入原始数值original_n，确保输出格式符合要求
• 完善基例：拦截所有小于4的非0数，避免无效递归
• 正确使用strtol：通过endptr校验输入是否为有效正整数
• 初始调用时i从0开始，保证倍数计数准确（如12减3次4到0，对应4*3=12）

内容的提问来源于stack exchange，提问作者Gabriel Burzacchini