Recursion Backtracking to print all combinations of binary numbers of length N without using loops

Question

Need help to print all combinations of binary digits using recursion and no loops.

void printBinary(int n)
{
    if(n==1)
    {
        cout << "0" << endl;
        cout << "1" << endl;
    }
    else 
    {
        // How do I call?
    }

}

Sample output for printBinary(3):

000
001
010
011
100
101
110
111

Answer 1

The problem in your recursion is you didn't save your answer

this part will give you difficulties:

if(n==1)
    {
         cout << "0" << endl;
         cout << "1" << endl;
    }

from those part, I think you want to "every state of recursion, print the correspondent digit, then after n-th recursion print the last digit"

It will be easier if you think "every state of recursion, decide the digit value then pass it to other state, then after n-th recursion print the passed value"

this is how I implement it in C++:

void bin(int n, string answer){
    if(n==0){
        cout << answer << endl;
    }else{
        bin(n-1, answer+"0");
        bin(n-1, answer+"1");
    }
}

and when you call it bin(3,"") it will give you:

000
001
010
011
100
101
110
111