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

How can i generate 4 bit binary combination using recursion in C for 0,1?

提问by shibly

For this array, trying something like this:

对于这个数组，尝试这样的事情：

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;
}

Expected output using recursion method:

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

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

Can't understand how to write that rec function. I have spent several hours to solve it. Can someone assist to write that function?

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

I am/was trying to do something like G_G posted below. How can i write such recursion function? Do i have to use one for loop to call that recursion function or two for loop with recursion or should i call the recursion function twice? For example:

我正在/正在尝试做类似下面发布的 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 ..
}

回答by zakinster

Simplest solution : binary conversion, no recursion

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

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

See MOHAMED's answerfor a recursive version of this loop

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

---

---

Binary recursion used by the following solutions

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

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

Recursive solution using char*buffer, no binary conversion

使用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);
    }
}

usage :

用法 ：

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

Recursive solution using only int, no buffer, no binary conversion

仅使用递归解决方案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);
    }
}

usage :

用法 ：

int_ten_rec(0, 1000);

Another version of this solution replacing tenpowerwidth bitwidth, replacing the printf widthwith a variable padding depending on the length variable. lengthcould be defined as a new parameter, a program constant, etc.

此解决方案的另一个版本替换tenpowerwidth bitwidth，width根据 length 变量将 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);
    }
}

usage :

用法 ：

int_rec(0, 4);

Tree Solution, recursive using char*buffer, no binary conversion

树解决方案，递归使用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);
    }
}

usage :

用法 ：

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

But this would print an additional 0at the begining of each line, to avoid this, build two smaller trees :

但这会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);

Recursive solution using int* array

使用 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");
    }
}

usage :

用法 ：

int_buffer_rec(4, 4);

回答by MOHAMED

the recursion could be done with +1

递归可以用 +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);
}

Execution:

执行：

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

回答by Gianluca Ghettini

just traverse DFS a binary tree of depth 4, going left is 0, going right is 1.

只需遍历 DFS 深度为 4 的二叉树，向左为 0，向右为 1。

tr(int dep, int val)
{
   if(dep == 4)
   {
     printf("\n");
   }
   else
   {
     printf("%d", val);
     tr(dep+1, 0); // going left
     tr(dep+1, 1); // going right
   }

   return;
}

int main()
{
   tr(0,0);
}

回答by Maxime Chéramy

I tried to limit my solution using to the same arguments but I would definitively add an extra argument to know the initial value of count.

我试图将我的解决方案限制为使用相同的参数，但我肯定会添加一个额外的参数来了解计数的初始值。

void rec(int val, int count) {
    if (count <= 1) {
        int i;
        int f = 0;
        for (i = sizeof(int) * 8; i >= 0; i--) {
            f |= (val >> i) & 1;
            if (f) {
                printf("%d", (val >> i) & 1);
            }
        }
        printf("\n");
    } else {
        rec(val * 2, count - 1);
        rec(val * 2 + 1, count - 1);
    }
}

Output:

输出：

1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111

In order to add the leading 0, I added an argument :

为了添加前导 0，我添加了一个参数：

#include <stdio.h>

void rec2(int val, int count, int b) {
    if (count <= 1) {
        int i;
        for (i = b - 1; i >= 0; i--) {
            printf("%d", (val >> i) & 1);
        }
        printf("\n");
    } else {
        rec2(val * 2, count - 1, b);
        rec2(val * 2 + 1, count - 1, b);
    }
}

void rec(int val, int count) {
    rec2(val, count, count);
}

int main() {
    rec(0, 4);
    rec(1, 4);
    return 0;
}

Output:

输出：

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

回答by autistic

Let us start by designing the prototype of the recursive function. Hopefully, it'll make sense from there. Take a look at a non-recursive version of this code, and you'll need the same variables. You don't need to pass anyof them as arguments, but I'd prefer to pass them all, and make the solution as flexible and modular as possible. Consider the return value, too. That should probably indicate some sort of success, in order to mimic consistency with the C standard library.

让我们从设计递归函数的原型开始。希望从那里开始有意义。查看此代码的非递归版本，您将需要相同的变量。您不需要将它们中的任何一个作为参数传递，但我更愿意将它们全部传递，并使解决方案尽可能灵活和模块化。还要考虑返回值。这可能表明某种成功，以模仿与 C 标准库的一致性。

int count_r(char *destination, /* The storage for the function to store *
                                *     the 0s and 1s as we count.        */
            size_t length,     /* The number of digits in the number.   */
            char *digit);      /* The set of digits                     */

---

---

Now let us focus on designing the first iteration. Like in primary school, we start by defining our count_rto iterate only single digits at a time. Once we can prove that it knows how to count from 0to 9, we introduce it to double digits... but for now, one step at a time.

现在让我们专注于设计第一次迭代。就像在小学一样，我们首先定义我们count_r一次只迭代一位数。一旦我们能够证明它知道如何从统计0到9，我们把它引进到两位数......但现在，一步一个脚印的时间。

Let us assume destinationis initialised to contain lengthbytes of digits[0], prior to the first call. This initialisation is done by the caller, and the caller would presumably output that pre-initialised array before calling. The first iteration should modify only one byte: The one indicated by length, and then return to the caller.

让我们假设在第一次调用之前destination被初始化为包含 , 的length字节digits[0]。这个初始化是由调用者完成的，调用者可能会在调用之前输出这个预先初始化的数组。第一次迭代应该只修改一个字节：由 指示的那个length，然后返回给调用者。

int count_r(char *destination, size_t length, char *digit) {
    /* The position of the right-most digit is before the '
int main(void) {
    char num[] = "0";
    do {
        puts(num);
    } while (count_r(num, strlen(num), "0123456789ABCDEF") == 0);
}
' in destination, *
     *     so we need to decrement length                                      */
    length--;

    /* Find the digit at the very end of destination, within our "digit" parameter */
    char *d = strchr(digit, destination[length]);

    /* d[1] points to the next digit (or '
void count_r(char *destination, size_t length, char *digit) {
    /* The position of the right-most digit is before the '
#include<iostream>
#include<cstdio>
using namespace std;
void rec(int val)
{
  if(val<16)
  {
    printf("%u%u%u%u", val>>3, (val&4)>>2, (val&2)>>1, val&1);
    printf("\n");
    rec(++val);    //calling val+1 here
  }
  return;
}
int main()
{
   rec(0);  //calling recursion for 0
}
' in destination, *
     *     so we need to decrement length                                      */
    if (length-- == 0) { return 1; }

    /* Find the digit at the very end of destination, within our "digit" parameter */
    char *d = strchr(digit, destination[length]);

    /* d[1] points to the next digit (or '
#include<iostream>
#include<cstdio>
using namespace std;
void rec(int val)
{
   if(val<16)
   {
     for(int b=val,a=8,i=0;i<4;b%=a,a/=2,i++)
     printf("%u",(b/a));
     printf("\n");
     rec(++val);// calling val+1 here
   }
   return;
}

int main()
{
   rec(0);//calling recursion for 0
}
') */
    if (d[1] == '
void printBinaryCombination(string str, int current)
{
    int length = str.length();
    if (length == 0)
        return;

    if (current == length)
        printf("%s\n", str.c_str());
    else
    {
        if (str[current] == '?')
        {
            str[current] = '0';
            printBinaryCombination(str, current+1);

            str[current] = '1';
            printBinaryCombination(str, current+1);

            // change back for next time
            str[current] = '?';
        }
        else
            printBinaryCombination(str, current+1);
    }
}
') {
        /* Set destination[length] to the first digit */
        destination[length] = digit[0];
        /* Recurse onto the next digit. We've already decremented length */
        return count_r(destination, length, digit);
    }

    destination[length] = d[1];
    return 0;
}
') */
    destination[length] = d[1];
    return 0;
}

The caller then presumably prints the array, and calls count_ragain with the same buffer to increment the counter. This works with different bases, and by reversing the digitstring we can decrement instead of incrementing. However, as we'll soon see, it fails after it reaches the highest number it can count to: 'F'in the example below.

然后调用者可能会打印数组，并count_r使用相同的缓冲区再次调用以增加计数器。这适用于不同的基数，通过反转digit字符串，我们可以减少而不是增加。但是，我们很快就会看到，它在达到可以计数的最高数字后失败：'F'在下面的示例中。

1000
1010
1100
1110

---

---

When the time comes for counting higher, d[1] will be '\0'as it will have iterated beyond the set of digits and into the null terminator for the string. Let us consider adding code to handle our second iteration.

当计数更高的时候，d[1] 将是'\0'因为它将迭代超出数字集并进入字符串的空终止符。让我们考虑添加代码来处理我们的第二次迭代。

A bit of code is needed to set destination[length]back to the first digitand recursively move left onto the next digit. This occurs when d[1] == '\0', so we can write an if (...) { ... }branch to handle that.

需要一些代码来设置destination[length]回第一个digit并递归地向左移动到下一个数字。这发生在 时d[1] == '\0'，因此我们可以编写一个if (...) { ... }分支来处理它。

There is a problem when lengthis passed in as 0, which we would discover after implementing the change mentioned just now. Here is where the function should return 1to indicating that counting has finished, because it has moved as far left as possible and reached the highest number possible.

当length作为0传入时有一个问题，我们在实施刚才提到的更改后会发现这个问题。这是函数应该返回1以指示计数已完成的地方，因为它已尽可能向左移动并达到可能的最高数字。

vector<string> ve,ve1;
int main(int argc, char const *argv[])
{
    /* code */
    int n;
    cin>>n;
    generate("0",n,true);
    generate("1",n,false);
    for(int i=0;i<ve.size();i++){
        cout<<ve[i]<<endl;
    }
    for(int i=0;i<ve1.size();i++){
        cout<<ve1[i]<<endl;
    }
    return 0;
}

After adding a few assertions (eg. assert(strlen(digit) > 1);) and writing some testcases, we might then decide that this function is ready for production. I hope I was able to help. :)

添加一些assert离子（例如assert(strlen(digit) > 1);）并编写一些测试用例后，我们可能会决定此功能已准备好用于生产。我希望我能帮上忙。:)

回答by MissingNumber

Recursion isa programming technique that allows the programmer to express operations in terms of themselves. In C and C++ , this takes the form of a function that calls itself.

递归是一种编程技术，它允许程序员用他们自己来表达操作。在 C 和 C++ 中，这采用调用自身的函数的形式。

void generate(string s,int n,bool b){
    if(n==1){
        if(b==true){
            ve.push_back(s);
        }
        else{
            ve1.push_back(s);
        }
        return;
    }else{
        generate(s+"0",n-1,b);
        generate(s+"1",n-1,b);
    }
}

This gives you exact output you want..!

这为您提供了您想要的确切输出..！

If you don't want to use bit shift operators ..

如果您不想使用位移运算符 ..

const int num=3;
string code="";

void GenerateBinaryCode(string str,unsigned int n){
    if(n==0){
        cout<<str<<endl;
    }
    else{
        str[num-n]='0';
        GenerateBinaryCode(str,  n-1);
        str[num-n]='1';
        GenerateBinaryCode(str, n-1);
    }
}
int main(){
    for(int i=0; i<num; i++)
        code+="x";

    GenerateBinaryCode(code,num);

}

回答by herohuyongtao

This problem can be generalized to obtain binary combination of any length by using recursion. For example, if you want to get all binary combinations of length=4, just call printBinaryCombination("????", 0)(i.e. four ?s need to replaced with 0or 1).

这个问题可以推广到使用递归获得任意长度的二进制组合。例如，如果要获取 的所有二进制组合length=4，只需调用printBinaryCombination("????", 0)（即?需要将 4 个替换为0或1）。

The corresponding code is as follows:

对应的代码如下：

#include<stdio.h>
#include<math.h>
#define MAXBITS 4
//#define MAXVALUES (((int)pow(2,maxb))-1)
const int MAXVALUES = (((int)pow(2,maxb))-1) //if this gives warning then use #define version.

void bin(int val,int total)
{
    int i = 0;          
    if(val <= MAXVALUES)            //can write pow(2,total-1)-1 but anyways..
    {
        for(i =0 ; i < total;i++)
        {
            printf("%d",!!(val&(int)pow(2,total-i-1)));
        }           
        printf("\n");

    }
    else return;
    bin(val+1,total);
}

int main()
{
    setbuf(stdout,NULL);
    bin(0,MAXBITS);//4 bits 
    return 0;
}

EDIT: Actually, the above function is also powerful to handle all binary combinations that contains random number of ?s, each of which can be 0or 1. For example, if you call printBinaryCombination("1??0", 0), it will print:

编辑：实际上，上面的函数对于处理包含随机数?s 的所有二进制组合也很强大，每个组合都可以是0或1。例如，如果您调用printBinaryCombination("1??0", 0)，它将打印：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXVALUES 15
#define MAXBITS 4
void bin(int val,int total) //@prototype void bin(int val);remove redundant total.
{
    char *s = malloc(sizeof(char)*(total+1)); //cant declare variable array(atleast pre c99)
    int i = 0;
    if(val <= MAXVALUES )
    {
        for(i =0 ; i < total;i++)
        {
        s[total - i-1] = !!(val&(int)pow(2,i)) + '0';
        }
        s[total] = '##代码##';
        printf("%s\n",s);
    }
    else return;
    bin(val+1,total);
}

int main()
{
    bin(0,MAXBITS);//4 bits 
    return 0;
}

回答by satishdd

To generate n bit combination you asked for(you asked for n=4) general recursive implementation for any n would be:

要生成您要求的 n 位组合（您要求 n=4），任何 n 的一般递归实现将是：

Main function:

主功能：

##代码##

Generate function which recursively generates the binary strings:

生成递归生成二进制字符串的函数：

##代码##

Hope this helps..

希望这可以帮助..

回答by abe312

This general purpose c++code works for any number of bits. just change const int num to any number of bits you want to generate binary code of...

此通用C++代码适用于任意数量的位。只需将 const int num 更改为您想要生成的二进制代码的任意位数...

##代码##

回答by Koushik Shetty

SOLN 1: a more generalized answer(compilable under c90, c99). booleans being output as int. Limitations :
1) uses math library.(its heavier so).

SOLN 1：更通用的答案（可在 c90、c99 下编译）。布尔值被输出为 int。限制：
1）使用数学库。（它更重）。

##代码##

Soln 2 :This can be done by char printing. no shift operator.

Soln 2：这可以通过字符打印来完成。没有移位运算符。

limitation(s) :
1) it can print(correctly) only upto 15(dec) or 0x0F(hex) values.
2) a total of
(5 * sizeof(char) * total) + (( total + 2) * (sizeof(int) + sizeof(int)))created on stack(so wasteful).

限制：
1）它只能（正确）打印最多 15(dec) 或 0x0F(hex) 值。
2）总共
(5 * sizeof(char) * total) + (( total + 2) * (sizeof(int) + sizeof(int)))在堆栈上创建（太浪费了）。

##代码##