how would you rewrite this recursive function to remove the recursion?

Question

I got that little function(I changed the name of variables)

Private Function everythingLinked(ByRef myClass As cls, ByVal found As Boolean) As Boolean
    If Not found AndAlso myClass.checked = False Then
        myClass.checked = True
        For i = 0 To myClass.numLink 
            If Not found Then
                found = everythingLinked(masterArrayOfCls(myClass.linkNum(i)), myClass.isMiddlePoint)
            End If
        Next
    End If

    Return found
End Function

I want to rewrite it so it would only be loop and no recursion and I'm currently lost, anyone could give me some direction or anything?

edit What it does. (English is not my native language sorry)

I'm passing a class to this function(with a starting value for found as false) to know if it is linked to the middle of the tree.

The class got an array with a maximum of 4 link to other class and it can be circular(this is why I have a checked_link boolean).

It does the recursion until there is no more link(return false) to check or until it find the middle link(return true).

edit

for an example, this

in pos 0 got link with 1
in pos 0 got link with 6
in pos 1 got link with 0
in pos 1 got link with 7
in pos 2 got link with 3
in pos 2 got link with 8
in pos 3 got link with 4
in pos 3 got link with 2
in pos 4 got link with 3
in pos 5 got link with 11
in pos 6 got link with 0
in pos 7 got link with 8
in pos 7 got link with 1
in pos 8 got link with 9
in pos 8 got link with 2
in pos 8 got link with 7
in pos 8 got link with 14
in pos 9 got link with 8
in pos 10 got link with 11
in pos 10 got link with 16
in pos 11 got link with 5
in pos 11 got link with 10
in pos 11 got link with 17
in pos 12 got link with 13
in pos 13 got link with 12
in pos 13 got link with 19
in pos 14 got link with 15
in pos 14 got link with 8
in pos 14 got link with 20
in pos 15 got link with 14
in pos 16 got link with 10
in pos 16 got link with 22
in pos 17 got link with 11
in pos 18 got link with 19
in pos 18 got link with 24
in pos 19 got link with 20
in pos 19 got link with 13
in pos 19 got link with 18
in pos 19 got link with 25
in pos 20 got link with 21
in pos 20 got link with 14
in pos 20 got link with 19
in pos 20 got link with 26
in pos 21 got link with 20
in pos 22 got link with 23
in pos 22 got link with 16
in pos 22 got link with 28
in pos 23 got link with 22
in pos 23 got link with 29
in pos 24 got link with 18
in pos 25 got link with 19
in pos 26 got link with 27
in pos 26 got link with 20
in pos 27 got link with 28
in pos 27 got link with 26
in pos 28 got link with 22
in pos 28 got link with 27
in pos 29 got link with 23

middlepoint would be pos 15

the code above can prove that every position can be linked with the middlepoint

so initial arg would be

  everythingLinked(random pos, false)

and in this case it would be always true

Answer 1

I could have this botched, but something like the following should remove the recursion. Basically you need to keep track of the current myClass instance and then move to the next one.

found = false
current = firstObj
While Not Found
  For i = 0 To myClass.numLink  
    If myClass.checked_link(i) = False Then 
      myClass.checked_link(i) = True 
      found = myClass.isMiddlePoint
    Else
      // looked through all items and need to break?
      Exit While
    End If 
  Next 

  current = masterArrayOfCls(myClass.linkNum(i))
WEnd

You'll need to add a condition in there to make sure you don't loop forever, maybe an else condition to the "If myClass.checked_link(i) = False" that indicates that you searched through the whole collection and need to break out of the loop.

Answer 2

Looking at the detail of this question here are some thoughts that may help.

You said that there was a maximum of 4 links and the first thing you need to do is determine the middle of the tree. So therefore if there are < 2 links than there is no "middle" . So the thought is that you only care if there are 3 or 4 links in the class being passed in.

It would be something like this:

if(numLinks >=3){
look at array[2] and/or array[3]
if(isFound == true){
// do something with it

Answer 3

In a general sense, a recursive routine can be replaced by a non-recursive routine by implementing the stack yourself.

Where you would normally make the recursive call, push the parameters that would normally be passed to the recursive function onto your stack. Then continue with the loop. When you hit the bottom of a recursion, pop off the data you need and continue down the next path. When the stack is empty, you are done.

Answer 4

It seems to me that you have a graph and you are performing a depth-first search to find a path from a specific node to a node which is a middle point.

If I've understood correctly, you do not need to have a checked_link property for each link, you just need a checked property for each node (what you call class) that you set when you start processing that node.

To remove the recursion, you will need an auxiliary data structure. If you want to preserve the algorithm you currently use, this will need to be a stack (but you can use a queue to make it a breadth-first search). You start by pushing the initial class onto the stack and marking it checked. Then, you loop for as long as the stack is non-empty, popping the top class from it and pushing all non-checked linked classes, marking each of them checked. Terminate the loop if at some point the popped class is a middle point, otherwise the stack emptying will signal that a middle point was not found.

(Sorry for not providing code, I am not sufficiently familiar with the language.)

Answer 5

thanks to everyone, this is what I did and it seem to work well

anyone see a problem with this?

Friend Function everythingLinked(ByVal myClass As cls) As Boolean
    Dim q As New Queue(Of cls)(_clsCount)
    Dim found = False

    myClass.checked_link = true
    found = myClass.isMiddlePoint
    q.Enqueue(myClass)

    While Not found AndAlso q.Count > 0
        Dim p = q.Dequeue
        For i = 0 To p.numLink
            If Not found AndAlso masterArrayOfCls(myClass.linkNum(i)).checked_link = false Then
                masterArrayOfCls(myClass.linkNum(i)).checked_link = true
                found = masterArrayOfCls(myClass.linkNum(i)).isMiddlePoint
                q.Enqueue(masterArrayOfCls(myClass.linkNum(i)))
            End If
        Next
    End While
    q.Clear()

    Return found
End Function