[RESOLVED] Converting recursion to iteration

[Troy Lundin]

Is it possible to make this function iterative or must it be recursive?

The Function traverses a grid of x length and y height. At each point in the grid, it checks all of it's neighbors to see if they are valid, meaning they exist in the grid and haven't been used yet.

The function works in it's current form but I was wondering if an iterative version would be more efficient.

PathManip is a Stringbuilder, stores the path currently being manipulated.
PathQueue is a List(Of String), stores all paths yet to be traversed.

IsPathAlreadyUsed is a boolean function that checks whether or not a specified point has been used in the current path.

    Sub FindNeighbors(ByVal coords As String)
        Dim x As Integer = CInt(coords(coords.Length - 2).ToString)
        Dim y As Integer = CInt(coords(coords.Length - 1).ToString)

        PathManip.Clear()
        PathManip.Append(coords)
        PathQueue.RemoveAt(0)     ' Remove the path from the queue since we are traversing it now.

        'Up
        If y - 1 >= 0 AndAlso Not IsPathAlreadyUsed(coords, x, y - 1) Then
            PathManip.Append(x & y - 1)
            If CheckWord(PathManip) Then
                PathQueue.Add(PathManip.ToString)
            End If
            PathManip.Remove(PathManip.Length - 2, 2)
        End If
        ' Up-right
        If y - 1 >= 0 AndAlso x + 1 <= xLimit AndAlso Not IsPathAlreadyUsed(coords, x + 1, y - 1) Then
            PathManip.Append(x + 1 & y - 1)
            If CheckWord(PathManip) Then
                PathQueue.Add(PathManip.ToString)
            End If
            PathManip.Remove(PathManip.Length - 2, 2)
        End If
        ' Right
        If x + 1 <= xLimit AndAlso Not IsPathAlreadyUsed(coords, x + 1, y) Then
            PathManip.Append(x + 1 & y)
            If CheckWord(PathManip) Then
                PathQueue.Add(PathManip.ToString)
            End If
            PathManip.Remove(PathManip.Length - 2, 2)
        End If
        ' Down-right
        If x + 1 <= xLimit AndAlso y + 1 <= yLimit AndAlso Not IsPathAlreadyUsed(coords, x + 1, y + 1) Then
            PathManip.Append(x + 1 & y + 1)
            If CheckWord(PathManip) Then
                PathQueue.Add(PathManip.ToString)
            End If
            PathManip.Remove(PathManip.Length - 2, 2)
        End If
        ' Down
        If y + 1 <= yLimit AndAlso Not IsPathAlreadyUsed(coords, x, y + 1) Then
            PathManip.Append(x & y + 1)
            If CheckWord(PathManip) Then
                PathQueue.Add(PathManip.ToString)
            End If
            PathManip.Remove(PathManip.Length - 2, 2)
        End If
        ' Down-left
        If x - 1 >= 0 AndAlso y + 1 <= yLimit AndAlso Not IsPathAlreadyUsed(coords, x - 1, y + 1) Then
            PathManip.Append(x - 1 & y + 1)
            If CheckWord(PathManip) Then
                PathQueue.Add(PathManip.ToString)
            End If
            PathManip.Remove(PathManip.Length - 2, 2)
        End If
        ' Left
        If x - 1 >= 0 AndAlso Not IsPathAlreadyUsed(coords, x - 1, y) Then
            PathManip.Append(x - 1 & y)
            If CheckWord(PathManip) Then
                PathQueue.Add(PathManip.ToString)
            End If
            PathManip.Remove(PathManip.Length - 2, 2)
        End If
        ' Up-left
        If x - 1 >= 0 AndAlso y - 1 >= 0 AndAlso Not IsPathAlreadyUsed(coords, x - 1, y - 1) Then
            PathManip.Append(x - 1 & y - 1)
            If CheckWord(PathManip) Then
                PathQueue.Add(PathManip.ToString)
            End If
            PathManip.Remove(PathManip.Length - 2, 2)
        End If

        ' If there are paths in the queue, traverse them.
        While PathQueue.Count > 0
            FindNeighbors(PathQueue(0))
        End While
    End Sub

[Shaggy Hiker]

You can certainly convert it to iteration, and it might actually be faster. Assuming that the code is tightly written, then there would be a slight overhead for each function call in the recursion. This would be a pretty minor cost, but it can certainly add up over many iterations. There is also a burden on the call stack, but that shouldn't matter unless you get Out of Memory errors.

However, there could be a greater inefficiency to a recursion: If you were to iterate through a grid, as you suggest, you would have two nested loops. By going through these loops, you would visit each cell once, so the number of iterations is Width * Height. If the recursion is well written, it will do no worse than that, but it will also do no better. On the other hand, poorly written recursion could cause some items to be revisited, which would mean that it could do MUCH worse.

That was written as a general rule, without looking at the specific code. Having looked at that, I wonder if the real question isn't one of efficiency. The code, as written, has several minor tweaks that can boost performance, such as:

Dim x As Integer = CInt(coords(coords.Length - 2).ToString)

This takes a length, which is an integer, turns it into a string, then turns it back into an integer. That's not good. A tighter writing would be:

Dim x as Integer = coords.Length-2

but an even tighter writing would be based on this realization: Strings are SLOW!!

There are lots of strings used in the code. You even have a stringbuilder to build stuff up. While a StringBuilder is certainly better than just concatenating strings, it is still bad. You will see FAR greater improvements by getting rid of strings than by anything else you can do. That might seem a bit difficult, and it may be. However, keep in mind that an ASCII string is actually just one byte per character. Therefore, you could use an array of bytes wherever you use a string. I don't know what you are recording, but it appears to be a pair of integers in all cases. If your grid size is less than 65000 in both dimensions, then you could use a List (of Integer) rather than a stringbuilder, and you could replace Append (x & y-1) with

.Add(x+(y<<16))

That would do the same thing and is faster, since it works with integers and not strings.

Another point would be that you appear to have Option Strict Off. You might see as much as a 50&#37; gain in performance just by turning Option Strict ON and fixing all the errors that pop up.

So those are some thoughts.

[Troy Lundin]

Ok, some explanation:

This is incorrect:

Dim x As Integer = CInt(coords(coords.Length - 2).ToString)

This takes a length, which is an integer, turns it into a string, then turns it back into an integer. That's not good. A tighter writing would be:

Dim x as Integer = coords.Length-2

What it is doing is grabbing the penultimate character in the string coords and storing it in x. Then, grabbing the last character in coords and storing it in y.

The reason: The coords are stored as a string with every character pair being a point. A string of "0102" would mean points {0,1} and {0,2}.

The code is pretty fast as it is, completing a six by six grid in mere seconds. I just read bad things about recursion and about iteration being faster and more efficient.

Also, how is (x & y-1) the same as (x+(y<<16))?
Thanks for your reply.

[Vectris]

What exactly are you trying to do with the code. I understand that your checking grid boxes surrounding a single box but what is the overall purpose?

[MaximilianMayrhofer]

Could you give a little background as to the context of your question? I have a feeling I might know what you are doing, but I don't want to post my alternative solution without completely understanding.

[minitech]

Ok, some explanation:

This is incorrect:


What it is doing is grabbing the penultimate character in the string coords and storing it in x. Then, grabbing the last character in coords and storing it in y.

The reason: The coords are stored as a string with every character pair being a point. A string of "0102" would mean points {0,1} and {0,2}.

The code is pretty fast as it is, completing a six by six grid in mere seconds. I just read bad things about recursion and about iteration being faster and more efficient.

Also, how is (x & y-1) the same as (x+(y<<16))?
Thanks for your reply.

More than instantly for 36 squares is bad. I have a password security check that can crack my password in 30 minutes.

This means you need to stop using strings to store your coordinates.

[VBDT]

The code is pretty fast as it is, completing a six by six grid in mere seconds. I just read bad things about recursion and about iteration being faster and more efficient.

I have never heard bad things about recursion. There are situations that recursion is the best method to use (searching binary trees for example). I do think that some people complain about recursion because they don't feel comfortably using them since they can be difficult to understand. You should use loop whenever you can but as I said there are situation when recursion is the best approach.

In your code I would optimize it by making numeric numbers be integers not strings. String data type is more slower than numeric data types.

[minitech]

You don't actually have to change the recursion to iteration (which would be harder), but you can optimize your code. Since it's a queue, why don't you use a Queue(Of List(Of Point)) instead of a List(Of String)? Or a Point instead of a String? (System.Drawing must be imported.) And why y-1 >= 0? Why not y > 0?

 Sub FindNeighbors(ByVal coords As Point)
        Dim x As Integer = coords.X
        Dim y As Integer = coords.Y

        PathManip.Add(coords)
        PathQueue.DeQueue() ' Remove the path from the queue since we are traversing it now.

        'Up
        If y > 0 AndAlso Not IsPathAlreadyUsed(coords, x, y - 1) Then
            PathManip.Add(New Point(x,y-1))
            If CheckWord(PathManip) Then _
                PathQueue.Add(PathManip.Clone())
            PathManip.RemoveAt(PathManip.Count - 1)
            PathManip.RemoveAt(PathManip.Count - 1) 'Remove last two
        End If
        ' Up-right
        If y > 0 AndAlso x < xLimit AndAlso Not IsPathAlreadyUsed(coords, x + 1, y - 1) Then
            PathManip.Add(New Point(x+1,y-1))

Etcetera.

[Troy Lundin]

You don't actually have to change the recursion to iteration (which would be harder), but you can optimize your code. Since it's a queue, why don't you use a Queue(Of List(Of Point)) instead of a List(Of String)? Or a Point instead of a String? (System.Drawing must be imported.) And why y-1 >= 0? Why not y > 0?

y - 1 because I am checking the next point. Checking if the point above where I am (figuratively speaking) is going to be on the grid.
I will look into using system.drawing.point and also using a queue. Would a Queue be faster than a List? Thanks for the input.

Also, more info on what I am trying to accomplish.
Say I start at coord {0,0}. I want to find every possible path from that starting point that does not use the same coord twice.

Ex. {0,0} {1,0} {1,1} (0,1} From there I can only go down or down-right since right, up-right and up have already been used and up-left, left and down-left are not possible.

[VBDT]

Are these picture coordinates?
Also you should define what path means. For example can path go from {0,0} to {1,1}?

[Shaggy Hiker]

What it is doing is grabbing the penultimate character in the string coords and storing it in x. Then, grabbing the last character in coords and storing it in y.

Yah, I was going too fast. It's still a string, though.

The code is pretty fast as it is, completing a six by six grid in mere seconds.

36 cells and you think that a couple seconds is acceptable? Your standards are too low

I wrote a genetic algorithm that made lots of sense using strings. After all, a genome would be a 'string' of genes, and for this particular genome, it really WAS a string. It worked, but I re-worked it to use only integers and the performance went up by an order of magnitude or more (I forget the exact speed up).

Also, how is (x & y-1) the same as (x+(y<<16))?
Thanks for your reply.

It isn't the same, it would be the equivalent step if you were to pack the X,Y into a single integer such that you could use a List (of Integer). It would put the Y into the two high bytes and the X in the two low bytes. Since the discussion has gone well beyond that, it isn't actually relevant any longer.

Working with a List or Queue of Points will work better than string, and about as well as integer (might even work better, since the + and << operators give you no advantage in .NET as they do in some lower level languages).

[minitech]

y - 1 because I am checking the next point. Checking if the point above where I am (figuratively speaking) is going to be on the grid.
I will look into using system.drawing.point and also using a queue. Would a Queue be faster than a List? Thanks for the input.

Also, more info on what I am trying to accomplish.
Say I start at coord {0,0}. I want to find every possible path from that starting point that does not use the same coord twice.

Ex. {0,0} {1,0} {1,1} (0,1} From there I can only go down or down-right since right, up-right and up have already been used and up-left, left and down-left are not possible.

Ok, y - 1 >= ... is subtraction, then comparaison. y > ... is just comparaison and does the same thing, so it's faster. It doesn't do much, but if you had a 1,000,000 x 1,000,000 grid, it might!

A System.Drawing.Point is also faster than a string.

A Queue is not faster than a List, but it makes more sense because you're currently using a List like a queue; why not make the code that much more readable?

After making those changes, does it speed up?

[minitech]

In fact, you could even take out this line:

PathQueue.DeQueue() ' Remove the path from the queue since we are traversing it now.

and put this for your While loop; also slightly faster then the two-step way:

        ' If there are paths in the queue, traverse them.
        While PathQueue.Count > 0
            FindNeighbors(PathQueue.DeQueue())
        End While

[Troy Lundin]

Ok, I switched everything to Point (so embarrassed to have not thought of that myself) and I got a 37.5% speed increase. Here is the new code.

    Sub Neighbors(ByVal Path As List(Of Point))
        Dim x As Integer = Path(Path.Count - 1).X
        Dim y As Integer = Path(Path.Count - 1).Y

        Dim Up As Point = New Point(x, y - 1)
        Dim UpRight As Point = New Point(x + 1, y - 1)
        Dim Right As Point = New Point(x + 1, y)
        Dim DownRight As Point = New Point(x + 1, y + 1)
        Dim Down As Point = New Point(x, y + 1)
        Dim DownLeft As Point = New Point(x - 1, y + 1)
        Dim Left As Point = New Point(x - 1, y)
        Dim UpLeft As Point = New Point(x - 1, y - 1)

        PathQ.RemoveAt(0)

        If y - 1 >= 0 AndAlso Not Path.Contains(Up) Then CheckPath(Path, Up) 'Up
        If y - 1 >= 0 AndAlso x + 1 <= xLimit AndAlso Not Path.Contains(UpRight) Then CheckPath(Path, UpRight) 'Up Right
        If x + 1 <= xLimit AndAlso Not Path.Contains(Right) Then CheckPath(Path, Right) 'Right
        If x + 1 <= xLimit AndAlso y + 1 <= yLimit AndAlso Not Path.Contains(DownRight) Then CheckPath(Path, DownRight) 'Down Right
        If y + 1 <= yLimit AndAlso Not Path.Contains(Down) Then CheckPath(Path, Down) 'Down
        If x - 1 >= 0 AndAlso y + 1 <= yLimit AndAlso Not Path.Contains(DownLeft) Then CheckPath(Path, DownLeft) 'Down Left
        If x - 1 >= 0 AndAlso Not Path.Contains(Left) Then CheckPath(Path, Left) 'Left
        If x - 1 >= 0 AndAlso y - 1 >= 0 AndAlso Not Path.Contains(UpLeft) Then CheckPath(Path, UpLeft) 'Up Left

        While PathQ.Count > 0
            Neighbors(PathQ(0))
        End While

    End Sub

Also, when I said "mere seconds" earlier I was exaggerating. My benchmarking puts 6x6 at ~0.85 seconds for the old method and ~0.55 seconds for the new method. I did a 100 x 100 grid in ~21 seconds.

Also note that I am checking for a dictionary key each time CheckPath is called. That may be why my numbers seem high.

[minitech]

I'm going to try to make my own.

[minitech]

Also try this and see how it turns out compared to the first with a 36 x 36 grid. Make PathQ a Queue(Of List(Of Point)).

 Sub Neighbors(ByVal Path As List(Of Point))
        Dim x As Integer = Path(Path.Count - 1).X
        Dim y As Integer = Path(Path.Count - 1).Y

        Dim ym1 As Integer = y - 1
        Dim yp1 As Integer = y + 1
        Dim xm1 As Integer = x - 1
        Dim xp1 As Integer = x + 1

        Dim Up As Point = New Point(x, ym1)
        Dim UpRight As Point = New Point(xp1, ym1)
        Dim Right As Point = New Point(xp1, y)
        Dim DownRight As Point = New Point(xp1, yp1)
        Dim Down As Point = New Point(x, yp1)
        Dim DownLeft As Point = New Point(xm1, yp1)
        Dim Left As Point = New Point(xm1, y)
        Dim UpLeft As Point = New Point(xm1, ym1)

        If y - 1 >= 0 AndAlso Not Path.Contains(Up) Then CheckPath(Path, Up) 'Up
        If y - 1 >= 0 AndAlso x + 1 <= xLimit AndAlso Not Path.Contains(UpRight) Then CheckPath(Path, UpRight) 'Up Right
        If x + 1 <= xLimit AndAlso Not Path.Contains(Right) Then CheckPath(Path, Right) 'Right
        If x + 1 <= xLimit AndAlso y + 1 <= yLimit AndAlso Not Path.Contains(DownRight) Then CheckPath(Path, DownRight) 'Down Right
        If y + 1 <= yLimit AndAlso Not Path.Contains(Down) Then CheckPath(Path, Down) 'Down
        If x - 1 >= 0 AndAlso y + 1 <= yLimit AndAlso Not Path.Contains(DownLeft) Then CheckPath(Path, DownLeft) 'Down Left
        If x - 1 >= 0 AndAlso Not Path.Contains(Left) Then CheckPath(Path, Left) 'Left
        If x - 1 >= 0 AndAlso y - 1 >= 0 AndAlso Not Path.Contains(UpLeft) Then CheckPath(Path, UpLeft) 'Up Left

        While PathQ.Count > 0
            Neighbors(PathQ.DeQueue())
        End While

    End Sub

[VBDT]

What exactly are you trying to do with the code. I understand that your checking grid boxes surrounding a single box but what is the overall purpose?

I think these questions make a lot of sense. We still don't know the answers to them.
Why not use hash tables which has a structure of grid? Why not have all this points to be objects that would have member variable that will hold boolean value to make the object as been "used" or not? There could be better ways of doing what you want, but we got to know what is that you are trying to achieve.

[Troy Lundin]

0.55 seconds with List, 1.23 seconds with Queue.

[minitech]

Really? That's interesting! I will be using a List from now on