Recursion challenge

[LooseCaboose]

Pseudo-code for iterative Gray code:

Code:

for i = 1 to n: a[i] = 0; d[i] = 1;
for i = 0 to n: up[i] = i;

do
  output();
  i = up[n];
  up[n] = n;
  a[i] = a[i] + d[i];
  up[i] = up[i - 1];
  up[i - 1] = i - 1;
  d[i] = -d[i];
loop until i = 0

a is the current Gray code, d is a direction array and the up array is used to jump across the tree to reduce the ammortized time to O(1). The recursive version is quite easy (but really difficult to analyse):

Code:

G(1) = {0, 1}
G(n) = 0G(n - 1)
     = 1G`(n - 1)

G`(1) = {1, 0}
G`(n) = 1G(n - 1)
      = 0G`(n - 1)

[Antoni Gual]

Well, you seem to be against recursion. It's slow and a stack hog but in problems involving a limited number of calls it can be the simplest solution. Obviously it's no good to calculate factorials but it's the best solution when a tree must be explored, as Moneo said.

Loose Caboose: Your floodfill example is only an exampe of a poor algorithm. It just generates calls without knowing if there is a former call for the same point. With an iterative implementation you should create a huge queue array or you would have a lot of gaps. There are much better ways to floodfill. The one you posted is good too teach what's floodfill, you can see it at a first glance.

To keep the thread open (and again not a good example of what recursion should be used on). A mcd calculation

Code:

DECLARE FUNCTION mcd& (a&, b&)
PRINT mcd&(320, 240)

FUNCTION mcd& (a&, b&)
c& = a& MOD b&
IF c& THEN
    mcd& = mcd&(b&, c&)
ELSE
   mcd& = b&
END IF
END FUNCTION

[Moneo]

I did not code and test your pseudo code for Gray Code, it looked too complicated. However, I found the following simple algorithm among my stuff.

Code:

REM Generate Gray Code bytes; i.e. values in range from 0 to 255.
DEFINT A-Z
FOR X=0 TO 255
        GRAY = X XOR (INT(X/2))
        rem Print or output the Gray Code value in GRAY.
NEXT X

Given the one line algorithm above, why would you want to do this recursively? Check it out, it works. You can generate bit patters wider than a byte, but the upper liimt of the FOR statement must end on a power of 2 (minus 1).
It's amazing how some programmers can complicate simple matters.
*****

[LooseCaboose]

The algorithms work differently, the ones I posted generate strings of zeros and ones representing the values in Gray code for any arbitary byte length. Your algorithm only works for powers of two and generates the corresponding integer values instead.

The algorithm I gave is (AFIAK) the one of the fastest general purpose gray code generation algorithms available. The way the algorithm works is also used in other algorithms for generating binary strings and permutations.

Recursive algorithms are just based on the principle of induction. The pseudo code for the recursive gray code I posted shows how each Gray code string is simply an extension of the previous one, with only the first case actually needing to be defined concretely.

[Moneo]

The algorithms work differently, the ones I posted generate strings of zeros and ones representing the values in Gray code for any arbitary byte length. Your algorithm only works for powers of two and generates the corresponding integer values instead.

If I wanted to generate strings of zeros and ones, I could add 3 or 4 lines of code to do this (I think I posted this somewhere before). But the point is that I don´t want to generate strings of 0 and 1, I want to generate bytes or words. The application that receives these bytes or words wants the binary representation of these bytes or words to conform to Gray Code, that is, that each one differs from the preceding by only one bit.

POWERS OF 2: My algorithm has an upper boundary of a power of 2 (minus 1) intentionally, so that the highest value generated wraps back (with only 1 bit change) to zero which is the first pattern of the next series (if you want to generate multiple series).

Also at issue here is the fact that I have used this algorithm twice in business for practical applications, not just for academic purposes.

Sorry, but I don't quite understand the rest of your argument.
What does AFIAK mean?
*****

[Hexadecimal Disaster]

In fact, is AFAIK: As Far As I Know. Acronyms, you see. :roll:

[LooseCaboose]

If I wanted to generate strings of zeros and ones, I could add 3 or 4 lines of code to do this (I think I posted this somewhere before). But the point is that I don´t want to generate strings of 0 and 1, I want to generate bytes or words.

Thats not what I said. I said the algorithms /work/ differently, your algorithm directly generates integer numbers, the algorithm I gave generates strings of ones and zeros by calculating one bit of the string at time. Conversion from string form to integer form and vice-versa is trivial. My algorithm is also general purpose, it can be used for /any/ byte length, yours can only be used for byte lengths that have a power of two. Whether or not a commercial application requires arbitary byte length is a different matter entirely, the point is that your algorithm is faster and simpler than the one I gave, but is far more limited.

Also at issue here is the fact that I have used this algorithm twice in business for practical applications, not just for academic purposes

How is this "at issue"? I never said that your algorithm is useless, indeed for a commercial application that only required generation of gray codes with a power of 2 byte length, your algorithm is definitely a sensible choice. However if a more general purpose solution is required to generate n-bit Gray codes, then your algorithm is no longer suitable.

Sorry, but I don't quite understand the rest of your argument.

Which part?

[Moneo]

LooseCaboose, I think we're deadlocked here. You like you "general purpose" algorithm, and I like mine.

I would like to coment regarding the issue of bytes or words that are not on a power of 2 boundary. I can remember the IBM 7094 which had a 36 bit word, the NCR 315 with a 35 or 37 bit word, and some minicomputer that had a 24 bit word. Other than those, all the machines I've seen, especially in the last generation, have bytes/words on a power of 2 boundary. This is not an argument; only an observation.
*****

[LooseCaboose]

LooseCaboose, I think we're deadlocked here. You like you "general purpose" algorithm, and I like mine.

No, I like both for different reasons. The decision of which of the two algorithms to use in practice is dependant on the situation at hand. This is why algorithms such as insertion sort are still used in commercial software today even though other sorting algorithms such as quicksort, mergesort and heapsort are much faster; because it works better for some tasks.

I'll agree that very few (if any) modern machines have word lengths that aren't a power of 2 in length, however a machines hardware word length isn't the only one you would use. For example the RS232 protocol uses 10bit words (8 bit data, 1 stop, 1 start bit) and Huffman codes use variable word lengths. Not so relevant in terms of Gray code generation, just pointing out that irregular word lengths are still very much in use. That said, in about 99% of real world cases, your algorithm would be the much better choice.

[Moneo]

Speaking about sorts, I don't know if you've noticed the following. Every QuickSort that I've seen does not retain any original sorted sequence. For example, let's say I have a file with fields like name and age, and I sort the file by name.

Now I do a QuickSort on the name sorted file by age. You would think that for records with the same age that the name would still be in sequence, because the input file to the QuickSort was in name sequence. WRONG. The original name sequence is destroyed by the QuickSort algorithm, thus violating an old industry standard. To get what you want, you would have to specify both age and name as sort fields to the QuickSort.

So, if you're substituting a QuickSort into a production job flow to get some extra speed, beware that original sort processes did not assume retention of any previous sequences.
*****