using recursion to generate all possible bitstrings of length n

I'm trying to make a 2d array filled with the truth table for n amount of variables

ex. 3 variables will create an array that looks like this

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

i'm having trouble coming up with a recursive algorithm to generate all possible bitstrings.
any help would be appreciated. thanks

hellow ..

instead of 2d array .. if u transform the problem in lists .(linklists ) problem will be solved easily .. i m doing it .. and will send u the solution if it works ..

Do you have to use recursion? For a truth table like this, each row is just the binary value of its row index:

0 - 0 0 0
1 - 0 0 1
2 - 0 1 0
3 - 0 1 1
4 - 1 0 0
5 - 1 0 1
6 - 1 1 0
7 - 1 1 1

But for a more general solution, recursion can be useful. One simple recursive solution is to pass the array of items and a length value (starting at the array length) to a recursive method that iterates over the array up to the length value, and for each index it swaps the item at the index with the one at length - 1, then calls itself, passing the array and length - 1, then repeats the previous swap.

If this is tricky to grasp, it might help to step through the algorithm on paper.

The hardest part of the software task is arriving at a complete and consistent specification, and much of the essence of building a program is in fact the debugging of the specification...
F. Brooks

How about converting int to binary string then separate ? This is obviously not a smart solution since you work with low level binary digit which later on works with string. It consumes so much resources and longer time complexity ;)

Quote:

---

Originally Posted by dlorde

But for a more general solution, recursion can be useful.

---

You mind explaining in details of the usefullness you find in this problem, don't you ?

Quote:

---

One simple recursive solution is to pass the array of items and a length value (starting at the array length) to a recursive method that iterates over the array up to the length value, and for each index it swaps the item at the index with the one at length - 1, then calls itself, passing the array and length - 1, then repeats the previous swap.

If this is tricky to grasp, it might help to step through the algorithm on paper.

---

That sounds descriptive but I am skeptical of its practicality. You care of posting some code for everyone to watch ?

Quote:

---

The hardest part of the software task is arriving at a complete and consistent specification, and much of the essence of building a program is in fact the debugging of the specification...
F. Brooks

---

I see this kind of memos in all of your posts, could you stop borrow people's quotes and spread them like plague in all of the thread you join in? If you want to show people your views, then write yourself one after each post. he color and people's words are beautiful but your act of borrowing looks like a formal art of stealing in disguise. Thanks :)

Quote:

---

Originally Posted by IRnick

i'm having trouble coming up with a recursive algorithm to generate all possible bitstrings.

---

Does this mean you had no problems with an iterative solution?

Quote:

---

Originally Posted by yuenqi

How about converting int to binary string then separate ? This is obviously not a smart solution since you work with low level binary digit which later on works with string. It consumes so much resources and longer time complexity ;)

---

So don't use it.

Quote:

---

You mind explaining in details of the usefullness you find in this problem, don't you ?

---

Your meaning isn't clear.

Quote:

---

That sounds descriptive but I am skeptical of its practicality. You care of posting some code for everyone to watch ?

---

If you don't think you can write the code yourself, you can find several examples online if you search. I didn't invent the algorithm. If you don't feel it's practical use another.

Quote:

---

I see this kind of memos in all of your posts, could you stop borrow people's quotes and spread them like plague in all of the thread you join in?

---

No. I put them there for amusement and interest. That's what quotes are for. Most opinions of them are positive. If you don't like them, you don't have to read them, or you can just skip my posts altogether.

Quote:

---

If you want to show people your views, then write yourself one after each post. he color and people's words are beautiful but your act of borrowing looks like a formal art of stealing in disguise. Thanks :)

---

I have put my own words there at various times, but I'm no great wordsmith. I think you'll find quoting is generally encouraged as long as proper attribution is given - much like open-source licensing ;)

Every human being has a right to hear what other wise human beings have spoken to him. It is one of the Rights of Men; a very cruel injustice if you deny it to a man!
Thomas Carlyle

Quote:

---

Originally Posted by dlorde

So don't use it.

Your meaning isn't clear.

If you don't think you can write the code yourself, you can find several examples online if you search. I didn't invent the algorithm. If you don't feel it's practical use another.

No. I put them there for amusement and interest. That's what quotes are for. Most opinions of them are positive. If you don't like them, you don't have to read them, or you can just skip my posts altogether.

I have put my own words there at various times, but I'm no great wordsmith. I think you'll find quoting is generally encouraged as long as proper attribution is given - much like open-source licensing ;)

Every human being has a right to hear what other wise human beings have spoken to him. It is one of the Rights of Men; a very cruel injustice if you deny it to a man!
Thomas Carlyle

---

Yes, you are right. Your posts to me are all great, and I like to read all of them.
You should not care about that member of sick chinese regime.
I find either the iterative approach or recursive one are just so fine to solve this problem. Time complexity probably is the same.
By the way you have the most special username among many in CG. Does it mean "a lord of d's" or "a super d" ?

Quote:

---

Originally Posted by Marie Mih

By the way you have the most special username among many in CG. Does it mean "a lord of d's" or "a super d" ?

---

Either, both, or none, as you like :p

Oddly enough, it's just a contraction of my real name, Dave Lorde :cool:

I blame my parents :D

Incidentally, is it just a co-incidence that your user name sounds like (is homophonic with) 'marry me' ?

The name of a man is a numbing blow from which he never recovers...
Marshall McLuhan

Quote:

---

Originally Posted by Marie Mih

I find either the iterative approach or recursive one are just so fine to solve this problem. Time complexity probably is the same.

---

Well, the lowest complexity is O(2^N) where N is the number of bits (in this case 3).

The standard iterative algoritm is to use a number of nested loops, one for each bit (in this case there would be 3). This can easily be turned into a recursive algorithm with the same complexity. In that case the recursive method, containing one loop, calls itself to the wanted depth (in this case 3).

So for a fixed N (like 3) you're correct. Both algorithms are "just so fine". But if you want N to be easily variable the recursive version is better. You just change N to another number. In the iterative version you need to modify the code so the number of nested loops corresponds to N.