Is there an efficient algorithm for iterating over binary strings where each of the reciprocal is enumerated exactly once?

For even $n$: For all strings $a$ of length $\frac n2$, for all strings $b$ of length $\frac n2$ with $b\le a$, generate $ab^{-1}$.

In pseudocode:

for a = 0 .. 1 << n/2 - 1
    for b = 0 .. a
        output (a << n/2) | reverse (b)

For odd $n$, you can do basically the same thing, but with special treatment for the middle digit.

Reversing bit strings is rather expensive, so you’ll probably want to use a look-up table for that.

Recursive solution
(might not be optimal. Recursion depth is $\frac{n}{2}$)

---

In each step in the recursion, we fix the first and the last character, denoted by $b_1,b_n$. to two cases:

1. $b_1 \neq b_n$
2. $b_1 = b_n$

First case

Solving the first case, is easy (If I'm not wrong). You set the first character to $0$, the last to $1$, (or $b_0=1,b_n=0$ but you don't need both!), and let the substring $b_2...b-{n-1}$ get all other $2^{n-2}$ options.

Second case

The second case, is a bit harder, so we solve it with recursion. We set the first an the last bit once to $0$, and once to $1$, and repeat the previous step.

You get the following recursion depth formula $$D(n) = 2D(n-2)$$

---

Important remark:
The way you want to represent the output is very important. It could easily reduce the depth formula to $D(n) = D(n-2)$

---

Another remark: I don't really see the direct connection, but this question really reminds me of Heap's algorithm, maybe it will give someone good ideas...