如何使用C中的递归生成4位二进制组合0,1？

Question

对于这个数组,尝试这样的事情:

void rollover(int val,int count) {  
    if(count==0) {
        return;
    }
    printf("%d ",val);
    count--;
    rollover(val,count);    
}
int main() {
    int arr[]={0,1};
    for(int i=0;i<=1;i++) {
        rollover(arr[i],4);
    }
    printf("\n");
    return 0;
}

使用递归方法的预期输出:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

无法理解如何编写rec函数.我花了几个小时来解决它.有人可以协助编写该功能吗？

我正在尝试做下面发布的G_G之类的事情.我怎么能写这样的递归函数？我是否必须使用一个for循环来调用递归函数,或者使用两个for循环来递归,还是应该调用两次递归函数？例如:

void rollover(int val,int count) {  
    if(count==0) {
        return;
    }
    printf("%d ",val);
    count--;
    rollover(val,count);
    //.. do something if necessary ..
    rollover(val,count);
    //.. do something if necessary ..
}

Answer 1

最简单的解决方案:二进制转换,无递归

for(int i = 0; i < 16: ++i) {
    printf("%u%u%u%u", i/8%2, i/4%2, i/2%2, i%2);  
}

有关此循环的递归版本,请参阅MOHAMED的答案

以下解决方案使用的二进制递归

          _ 000
   _ 00 _/
  /      \_ 001
 0        _ 010
  \_ 01 _/
         \_ 011
          _ 100
   _ 10 _/
  /      \_ 101
 1        _ 110
  \_ 11 _/
         \_ 111

使用char*缓冲区的递归解决方案,没有二进制转换

void char_buffer_rec(char number[4], int n) {
    if(n > 0) {
        number[4-n] = '0';
        char_buffer_rec(number, n - 1);
        number[4-n] = '1';
        char_buffer_rec(number, n - 1);
    }
    else {
        printf("%s\n", number);
    }
}

用法:

char number[5] = {0};
char_buffer_rec(number, 4);

仅使用递归解决方案int,无缓冲区,无二进制转换

void int_ten_rec(int number, int tenpower) {
    if(tenpower > 0) {
        int_ten_rec(number, tenpower/10);
        int_ten_rec(number + tenpower, tenpower/10);
    }
    else {
        printf("%04u\n", number);
    }
}

用法:

int_ten_rec(0, 1000);

此解决方案的另一个版本替换tenpower宽度bitwidth,width根据长度变量用可变填充替换printf .length可以定义为新参数,程序常量等.

void int_rec(int number, int bitwidth) {
    static int length = bitwidth;
    int i, n;
    if(bitwidth > 0) {
        int_rec(number, bitwidth-1);
        /* n := 10^(bitwidth-2) */
        for(i=0,n=1;i<bitwidth-1;++i,n*=10);
        int_rec(number + n, bitwidth-1);
    }
    else {
        /* i := number of digit in 'number' */
        for(i=1,n=number;n>=10;++i,n/=10);
        /* print (length-i) zeros */
        for(n=i; n<length; ++n) printf("0");
        printf("%u\n", number);
    }
}

用法:

int_rec(0, 4);

树解决方案,使用char*缓冲区递归,无二进制转换

struct Node {
    int val;
    struct Node *left, *right;
};

void build_tree(struct Node* tree, int n) {
    if(n > 0) {
        tree->left = (Node*)malloc(sizeof(Node));
        tree->right= (Node*)malloc(sizeof(Node));
        tree->left->val = 0;
        build_tree(tree->left, n - 1);
        tree->right->val = 1;
        build_tree(tree->right, n - 1);
    }
    else {
        tree->left = tree->right = NULL;
    }
}

void print_tree(struct Node* tree, char* buffer, int index) {
    if(tree->left != NULL && tree->right != NULL) {
        sprintf(buffer+index, "%u", tree->val);
        print_tree(tree->left, buffer, index+1);
        sprintf(buffer+index, "%u", tree->val);
        print_tree(tree->right, buffer, index+1);
    }
    else {
        printf("%s%u\n", buffer, tree->val);
    }
}

用法:

    char buffer[5] = {0};
    Node* tree = (Node*)malloc(sizeof(Node));
    tree->val = 0;
    build_tree(tree, 4);
    print_tree(tree, buffer, 0);

但是这会0在每行的开头打印一个额外的,为了避免这种情况,构建两个较小的树:

    Node* tree0 = (Node*)malloc(sizeof(Node));
    Node* tree1 = (Node*)malloc(sizeof(Node));
    tree0->val = 0;
    tree1->val = 1;
    build_tree(tree0, 3);
    build_tree(tree1, 3);
    print_tree(tree0, buffer, 0);
    print_tree(tree1, buffer, 0);

使用int*数组的递归解决方案

#define MAX_LENGTH 32
int number[MAX_LENGTH];
void int_buffer_rec(int n, int length) {
    if(n > 0) {
        number[length - n] = 0;
        int_buffer_rec(n - 1, length);
        number[length - n] = 1;
        int_buffer_rec(n - 1, length);
    }
    else {
        for(int i = 0; i < length; ++i) {
            printf("%u", number[i]);
        }
        printf("\n");
    }
}

用法:

int_buffer_rec(4, 4);

Answer 2

递归可以用 +1

void f(unsigned int x)
{
   printf("%u%u%u%u\n",
          (x>>3)&0x1,
          (x>>2)&0x1,
          (x>>1)&0x1,
          x&0x1);
   if(x==0xF) return;
   else f(x+1);
}

int main(void)
{
    f(0);
}

执行:

$ ./test
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111