binary code list by recursion

[sedawk]

how to use *recursion* to generate binary code list. For example, binary(3) will generate:

000
001
010
011
100
101
110
111

I was thinking using this: in the above example, the last column 0 and 1 flipping by interval 1, the middle column 0 and 1 flip by interval 2, etc. So that it is possible to program recursively in terms of column-wise. It has advantage that it is possible to manipulate each column, eg., instead of changing flipping pattern from "0->1" to "1->", etc. So if this approach resolved, other pattern can be done similarly too.

However, I am not satisfied by this approach: it requires a lot of memory storage before the real output. All columns have to be stored in order to display the results. When the number of bits getting larger, that is no good. So there should be a way to do it row-wise.

It should have a easier way to do that recursively.

 

[Salem]

So what's wrong with

int i, limit;
limit = 1 << 3;
for ( i = 0 ; i < limit ; i++ ) {
  // output i in binary
}

Apart from it not being recursive that is.
Recursion is just going to make it far more messy that it need be.

--

 

[sedawk]

Nothing wrong with your code in terms of functionality. It still can produce the code table.

Recursion here can simply other code generation. Let's define the above binary code be standard binary code. Through recursion trick, other codes can be define using the same way as the standard code.

 

[dchoulette]

A recursive way to describe the problem:
- binary(1) is the set ('0' ,'1')
- binary is all elements of binary(n-1) with a '0' prepended followed by all elements of binary(n-1) with a '1' prepended.

--------------------

Denis

 

[Zyrenthian]

void OutputBinary(int n)
{
RecursiveOutput(pow(2,n)-1);
}

in RecursiveOutput, all you now need to do is a -- to the parameter until it is zero (ouput for zero as well and then return). For 3, pow will return 8. The 3 is actually the number of binary digits so pow(2,n)-1 will be 7 or 111 in binary.

Hope that helps.

Matt

 

[Zyrenthian]

By the way... a recursive call to output binary may blow the stack for larger values of n.

Matt

 

[lionelhill]

Salem's still right, though. You don't need recursion to do what you want to do, and it will make the problem harder.

If you want a code table consisting of n digits (let's say 2), each of which can belong to a set (let's say "a", "e" and "q"), and you want to generate a table by selecting each of these in order then (1) yes, you can do it recursively, but (2) you might just as well say we need set-size ^ number-of-digits combinations (=3^2 = 9)
Therefore do x = 1 to number-of-combinations (9),
for each x, find x mod digit-set-size (3) and translate that into a digit (in our case mod 3, 0="a", 1="e", 2="q"), and then divide x by digit-set-size (3) and so on, as many times as we expect digits (2). Then next x.

This is a simple piece of code with 2 for-next loops nested, a single power calculation, and a character array to do the digit translation.

If you want to be able to generate codes where the digits don't always happen in the same order (e.g. Gray codes etc.), then you're not going to be able to use recursion in a simple way as each instance of the recursive function may have to return characters in a different order.

 

[sedawk]

> If you want to be able to generate codes where the >digits don't always happen in the same order (e.g. Gray >codes etc.), then you're not going to be able to use >recursion in a simple way as each instance of the >recursive function may have to return characters in a >different order.

That is exactly the point to use recursion in the standard binary code so that the same algorithm can be use in Gray code generation. Note that in the Gray code with bit no. = 3, we have

000
001
011
010
110
111
101
100

take the last column, it flips [0,1] to [1,0]. The same pattern repeats in the other columns. The only difference is the flipping compared to the standard binary code generation.

 

[lionelhill]

OK, put it this way.

dchoulette quite correctly desribed a good way to use recursion.

quote:
A recursive way to describe the problem:
- binary(1) is the set ('0' ,'1')
- binary is all elements of binary(n-1) with a '0' prepended followed by all elements of binary(n-1) with a '1' prepended

Now take a look at your Gray code above. Although the bits do flip from 0 to 1 at ever halving frequencies, they all need to start at a different phase, which is not an automatic feature of recursion. You can put it in, but it's still over-complicated.

If you want Gray codes, there are many obvious ways to do it. 10sec thought: For codes of up to n bits, start with an array of n counters. Each counter counts how many 1's or 0's we've had in the corresponding digit. Initialise each with values 1, 2, 4, 8 etc. (lowest digit gets 1).
Now loop for each Gray code generated (i.e. 16 times for 4 bits).
add 1 to each number in the array. If it reaches 2^x where x is its position in the array (starting at 1) then reset it to zero and change digit 1<>0. Print the 1s and 0s appropriate for the current state. Then next.

I suspect that if you do come up with a recursive solution it will be a version of the method above, with each level of recursion corresponding to a number in the counter array. But why muck around with stack frames just to create an array?

 

[dchoulette]

I do not know if you should or should not use recursion but here is ...

A recursive way to describe the gray code generation:
- gray_code(1) is the set ('0' ,'1')
- gray_code is all elements of gray_code(n-1) in increasing order with a '0' prepended followed by all elements of gray_code(n-1) in decreasing order with a '1' prepended

--------------------

Denis