C语言编程题使用递归计算一个整数的二进制表示

1、基本递归实现

最直接的方法，通过不断地将整数除以2并获取其余数来构造二进制表示。

#include <stdio.h>

void printBinary(int n) {
    if (n > 1) {
        printBinary(n / 2);
    }
    printf("%d", n % 2);
}

int main() {
    int number = 10;
    printf("Binary representation of %d is: ", number);
    printBinary(number);
    return 0;
}

2、尾递归优化

尾递归是一种特殊的递归形式，优化后可以减少函数调用的开销。这里使用辅助函数来实现尾递归。

#include <stdio.h>

void printBinaryTailRecursive(int n, char *binary, int index) {
    if (n > 1) {
        printBinaryTailRecursive(n / 2, binary, index - 1);
    }
    binary[index] = '0' + (n % 2);
}

void printBinary(int n) {
    char binary[32];
    printBinaryTailRecursive(n, binary, 31);
    binary[32] = '\0';
    printf("%s", binary + (32 - (int)log2(n) - 1));
}

int main() {
    int number = 10;
    printf("Binary representation of %d is: ", number);
    printBinary(number);
    return 0;
}

3、通过位运算的递归实现

利用位运算符，可以直接获取一个整数的最低位（二进制位）。

#include <stdio.h>

void printBinaryBitwise(int n) {
    if (n > 1) {
        printBinaryBitwise(n >> 1);
    }
    printf("%d", n & 1);
}

int main() {
    int number = 10;
    printf("Binary representation of %d is: ", number);
    printBinaryBitwise(number);
    return 0;
}

4、使用递归反向构建二进制字符串

在递归调用的返回阶段逐步构建最终的二进制字符串。

#include <stdio.h>
#include <string.h>

void buildBinaryString(int n, char *binary, int index) {
    if (n > 0) {
        binary[index] = '0' + (n % 2);
        buildBinaryString(n / 2, binary, index - 1);
    }
}

void printBinary(int n) {
    char binary[32] = {0};
    buildBinaryString(n, binary, 31);
    printf("%s", binary + (31 - (int)log2(n)));
}

int main() {
    int number = 10;
    printf("Binary representation of %d is: ", number);
    printBinary(number);
    return 0;
}

5、使用递归计算反向二进制并反转输出

先计算出反向的二进制表示，然后反转字符串输出。

#include <stdio.h>
#include <string.h>

void reverse(char *str) {
    int n = strlen(str);
    for (int i = 0; i < n / 2; i++) {
        char temp = str[i];
        str[i] = str[n - i - 1];
        str[n - i - 1] = temp;
    }
}

void buildBinaryReverse(int n, char *binary, int index) {
    if (n > 0) {
        binary[index] = '0' + (n % 2);
        buildBinaryReverse(n / 2, binary, index + 1);
    }
}

void printBinary(int n) {
    char binary[32] = {0};
    buildBinaryReverse(n, binary, 0);
    reverse(binary);
    printf("%s", binary);
}

int main() {
    int number = 10;
    printf("Binary representation of %d is: ", number);
    printBinary(number);
    return 0;
}