im trying to write a recursive algorithm to generate the following binary sequence.

ie basically:

for 3:

i tried the iterative method, it works fine.
this is what i did:

for (i = 0 to pow(2, n) ) {
       //generate the binary form of no.

However, when i tried the following method(recursion) it does not work:

#include <iostream>
using namespace std;
int arr[10];
void pattern(int level, int a)
        int i;
        if (level == 2) {
                for (i = 0; i < 2; i++) {
                        cout << arr[i];
                cout << endl;
        } else {
                for (i = 0; i < 2; i++) {       
                        arr[i] = !arr[i];               
                        pattern(level + 1, arr[i]);     
int main()
        pattern(0, 1);
        return 0;

It works for the above value(ie n = 2). But does not work for higher values. Can anyone please help?


easy way out :

void doIt(int start, int end){
  if(start < end){
  else doIt(start+1,end);

You do realize that all you are doing is to print the values from 0 to x, where x = 2^k, k being a positive integer.
firstPerson posted a recursive algorithm which however only prints binary once. The correct recursive algorithm to print numbers from start(0) to end(x), would go something like:

1. if(start < end)
     a. printBinary(start)
     b. doIt(start+1,end)

The only thing required is to sort out the printBinary() which is real easy(try google-ing). I however, do not get you way to print binary.

P.S. You do not need an array till k=16 (for short) & k=32(for int). Just print their binary.

Thanks for the help nbaztec, firstPerson :) i got it.

>>firstPerson posted a recursive algorithm which however only prints binary once
oops, the doIt() is supposed to go inside the if statement.

>>firstPerson i got it

Good job.