Thread: Converting a recursion to iteration

The question is withdrawn.

The largest array you can allocate is 2^31 - 1, much smaller than 10e9.

What is it your algorithm is trying to do? It is possible that accomplishing such a task via brute strength simply isn't possible either recursively or iteratively.

Is what you want an iterative tree traversal algorithm? That isn't too hard to make iterative.

All you need to do is to design a state machine with the following transitions:

START:
- if there is a left child of the root, go to it and transition to DOWN_LEFT
- otherwise, if there is a right child of the root, go to it and transition to DOWN_RIGHT
- otherwise, print the root and return.
DOWN_LEFT:
- if there is a a left child, go left and stay in DOWN_LEFT
- otherwise, if there is a right child, go right and transition to DOWN_RIGHT
- otherwise, print the node, go to the parent, and transition to UP_RIGHT
UP_RIGHT:
- if there is a right child, go right and transition to DOWN_RIGHT
- otherwise, print the node, go to the parent, and stay in UP_RIGHT (or halt if in the root)
DOWN_RIGHT:
- if there is a left child, go left and transition to DOWN_LEFT
- otherwise, if there is a right child, go right and stay in DOWN_RIGHT
- otherwise, print the node, go to the parent, and transition to UP_LEFT
UP_LEFT:
- if this is the right child of some node, go to that node and stay in UP_LEFT
- if this is the left child of some node, go to that node and transition to UP_RIGHT
- if this is the root, print the root and halt

Say we have the tree with 1 in the root, 2 and 3 as 1's left and right children, and 4, 5, 6, and 7 as the left and right children of 2 and 3, respectively. I illustrate the machine starting from root (1). I represent each state as an ordered pair (node, state).

(1, START)
(2, DOWN_LEFT)
(4, DOWN_LEFT)
(2, UP_RIGHT) => print 4
(5, DOWN_RIGHT)
(2, UP_LEFT) => print 5
(1, UP_RIGHT) => print 2
(3, DOWN_RIGHT)
(6, DOWN_LEFT)
(3, UP_RIGHT) => print 6
(7, DOWN_RIGHT)
(3, UP_LEFT) => print 7
(1, UP_LEFT) => print 3
halt => print 1

If you prefer that the nodes be visitited in some similar order, you should be able to modify the algorithm to walk a bit differently. I think you will agree that, under this scheme, each node is visited a maximum of three times (precisely: each node is visited n+1 times, where n is the number of children of the node). So for a binary tree we are talking about O(3n) = O(n) running time, with O(1) storage...

I'm really not sure I understand what you're asking for... why do these iterative solutions not work?

After looking at your code a little more carefully, I think I might have deciphered what you are trying to do.

You want to generate all d-bit binary numbers which are solutions. You could simply generate all d-bit binary numbers and check them, but that would be prohibitively expensive. Therefore, you use a property of solutions that you can tell when a partial solution has been obtained. You want to skip all strings which have as a prefix a string which is not a partial solution, thereby vastly reducing the number of checked d-bit values (indeed to exactly the number of d-bit solutions).

Ok. Here's some pseudocode that I think might be a start.



- Start off with p = 1, d = 0, and s = 0^n.

while p > 0 do
- if d = 2, let p := p - 1, d := x + 1 such that x is the (p - 1)th digit of s.
- otherwise, do all of the following:
- replace the pth digit of s with d.
- if the first p digits of s constitute a partial solution, and p < n, then let p := p + 1, d = 0.
- elseif the first p digits of s constitute a partial solution, and p = n, then s is a solution. now let d := d + 1.
- elseif the first p digits of s do not constitute a partial solution, let d := d + 1.


Let's try this with, say, n = 3. We start with p = 1 and d = 0, and s = 000.

d < 2, so we go to the else clause.
we therefore replace the 1st digit of s with 0, obtaining s = 000.
say for the sake of argument that the first digit of s = 000 does constitute a partial solution. we let p = 2 and d = 0.
the loop iteration is now over.

d < 2 so we go to the else clause.
we therefore replace the 2nd digit of s with 0, obtaining s = 000.
say for the sake of argument that the first two digits of s = 000 do constitute a partial solution. we let p = 3 and d = 0.
the loop iteration is now over.

d < 2 so we go to the else clause.
we therefore replace the 3rd digit of s with 0, obtaining s = 000.
say for the sake of argument that the first three digits of s = 000 do constitute a partial solution. then 000 is a solution. we let d = 1.
the loop iteration is now over.

d < 2 so we go to the else clause.
we therefore replace the 3rd digit of s with 0, obtaining s = 001.
say for the sake of argument that the first three digits of s = 001 do not constitute a solution. then 001 is not a solution. we let d = 2.
the loop iteration is now over.

d = 2 so we let p = 2 and d = 1 (because x = 0, the 2nd digit of s, and d = x + 1).
the loop iteration is now over.

d < 2 so we go to the else clause.
we replace the 2nd digit of s with 1 to get s = 011.
say for the sake of argument that the first two digits of s = 011 do not constitute a partial solution. then let p = 2 and d = 2.
the loop iteration is now over.

d = 2, so we let p = 1 and d = 1.
the loop iteration is now over.

etc.

You probably see how it works. Is this what you're after? Notice that you really don't need a counter, per se, since the binary representations themselves should be enough to give you the decimal representation. Let me know if this is closer to what you were looking for. The translation to Java should be straightforward, but let me know if you want some proper pseudocode to look at.

Just out of curiosity, does my algorithm do what you want? I'm still not sure I've even understood what you're trying to do.

And correct me if I'm wrong, but how does your start() function know where the end of the sequence is? Won't it just overshoot it as you have currently implemented it? You don't use 'n' anywhere inside it.

Also, if you want to talk about efficiency, my algorithm does it with O(1) storage. Not that yours is inefficient in this respect, just saying.

Just so you can test it out without too much work, here's a Java implementation:

   void start()
   {
      int p = 0;
      byte d = 0;
      for(int i = 0; i < n; i++)
         sequence[i] = 0;
 
      while(p > -1)
      {
         if(d == 2)
         {
            p = p - 1;
            if(p > -1)
               d = sequence[p] + 1;
         }
         else
         {
            sequence[p] = d;
            if(!isPartialSolution(p))
            { // have no solution or partial solution
               d = d + 1;
            }
            else if(p = n)
            { // p = n, have a complete solution
               printSequence();
               d = d + 1;
            }
            else
            { // p < n, have a partial solution
               p = p + 1;
               d = 0;
            }
         }
      }
   }

I think that should be a faithful implementation. Also, yours should be fixable to account for the array length if that is a problem. Just something to think about...

Also, you might be clearer in the future when you are asking for help. There is no actual binary tree involved here, at best, just a hypothetical binary tree that you can think of as containing as paths strings of binary digits of length n. This is more easily couched in terms of strings (or arrays if you like), and both of our algorithms work this way.

How selective is your isPartialSolution() function? It had better be pretty selective if you want this scheme to work for any reasonable n.

"The code that I posted above is correct and there is no need to include n in the loop. You are welcome to run it and see for yourself that it stops."
- I think I now understand that you avoided checking the length in your algorithm by changing the definition of "partial solution" to mean strictly partial, as in, not complete. I hadn't realized you had redefined what it meant for a sequence to be a partial solution. Personally, I feel that this is sort of a kludge in the sense that you're redefining the natural problem definition (or at least what I very meagerly understood to be the problem) to suit implementation. Dirty, but I'll allow it.

"Your program produces array of integers."
I don't quite understand your objection to my algorithm's producing arrays of integers. An array of integers where all integers are either 0 or 1 is in fact a representation of a sequence of binary digits. The array [0, 1, 0, 0, 1] can easily be interpreted as the binary string 01001 and using any method of converting bases translated to 9 in base 10. So long as printSequence() is called every time the array contains a representation of a binary string which is a partial solution, I don't see a problem. As I demonstrated by hand previously, my algorithm seems like it is doing the right thing for the case n=3 and for a certain hypothetical isPartialSolution() function. Is that algorithm not doing the right thing?

I suppose I was sloppy when I said my algorithm is O(1). Technically, since it uses the global variable sequence[], it is O(n) where n is the number of things in sequence. The convention on this is normally to ignore global, static-size structures in algorithmic analysis, but since this structure just happens to be the same size as the problem size, that's probably not fair. In that sense, my algorithm is an O(n) storage algorithm. However, what I meant to say is that your state array is not necessary... it is redundant.

"There must be some state information to backtrack to!"
- Yes, here it is the sequence. The state array is not required.

I don't have access at the moment to a compiler, but I still tend to think the algorithm is correct, whatever the results of the proposed implementation are. I would appreciate it if you were to take a look at my post #6 to tell me at what stage the algorithm does something wrong.

Huh. Just implemented my version using javascript. I let n = 3 and made isPartialSolution the "true" function. Here's the output:

000
001
010
011
100
101
110
111

Is this not what you wanted? Let me now change isPartialSolution to return true except for strings starting with 10:

000
001
010
011
110
111

I'm really sorry, I'm convinced my algorithm works. There were a few problems with my implementation, but they were really easy to fix... just standard problems when one takes 1-indexed pseudocode and transforms it to an actual programming language. If you want me to try out any further examples, more complicated ones for larger n, say, let me know. I can also give you the cheap .html file with the implementation if you want it.

And I'll take your word for it that your implementation works... I believe after restructuring your code to better adhere to structured programming style our code would look more similar (I make reference to the while(true) and break combo). This was actually a pretty interesting (if trivial) problem... thanks for posting it. I'm sure a lot of people who just read this forum will learn a lot from the discussion...

^ Just a clarification, my algorithm is already posted above and works (I'll leave as an exercise to the reader what needs to be changed about the java implementation to make it work).