Recursive Sub Calls and Stack Overflow

[dreid1011]

I've been playing around with some maze generating VBA and I run out of space about 3/4 of the way through the maze at 10x20 size. It will finish 10x10 maze just fine.

Then after some searching I came across a test to see what my limits might be for recursive calls:

Is there a call stack level limit?

I have a couple of colleagues looking at some bad code in Excel VBA, wondering is there a limit to the number of levels in a call stack

stackoverflow.com

Dim count As Integer

Sub Rec()
    count = count + 1
    Cells(1, 1) = count
    Call Rec
End Sub

With this I was able to get about 37k loops before the overflow. I then tested it without the variable and wrote directly to the cell and I had to stop it over 2B loops because I had other work to do.

Cells(1, 1) = 0
Sub Rec()
    Repeat:
    Cells(1, 1) = Cells(1, 1) + 1
    GoTo Repeat
End Sub

So now I tried to eliminate all the variables in the code from the youtube link above in favor of writing directly to the sheet, but that didn't seem to help much. (code below before eliminating all variables)

Option Explicit
Dim r As Integer, c As Integer
Sub InitMaze()
With Range("B2:U11")
    .Borders.Weight = xlThick
    .Interior.Color = vbBlack
End With
r = 2: c = 2
Call CaveMaze
End Sub

Sub CaveMaze()
Repeat:
Dim direc As Integer, LoopCount As Integer

If Cells(r, c).Interior.Color = vbBlack Then
    Cells(r, c).Interior.Color = vbBlue
End If

LoopCount = 0

DoEvents

Do
    Randomize
    direc = Int((Rnd * 4) + 1)
    If direc = 1 And Cells(r + 1, c).Interior.Color = vbBlack Then
        Cells(r, c).Borders(xlEdgeBottom).LineStyle = xlLineStyleNone
        r = r + 1
        Exit Do
    ElseIf direc = 2 And Cells(r, c + 1).Interior.Color = vbBlack Then
        Cells(r, c).Borders(xlEdgeRight).LineStyle = xlLineStyleNone
        c = c + 1
        Exit Do
    ElseIf direc = 3 And Cells(r - 1, c).Interior.Color = vbBlack Then
        Cells(r, c).Borders(xlEdgeTop).LineStyle = xlLineStyleNone
        r = r - 1
        Exit Do
    ElseIf direc = 4 And Cells(r, c - 1).Interior.Color = vbBlack Then
        Cells(r, c).Borders(xlEdgeLeft).LineStyle = xlLineStyleNone
        c = c - 1
        Exit Do
    End If

    LoopCount = LoopCount + 1

    If LoopCount > 9 Then
        Call BackTrack
        Exit Sub
    End If

Loop

GoTo Repeat

End Sub

Sub BackTrack()
Cells(r, c).Interior.Color = vbWhite

If Cells(r + 1, c).Interior.Color <> vbWhite And Cells(r, c).Borders(xlEdgeBottom).LineStyle = xlLineStyleNone Then
    r = r + 1
ElseIf Cells(r, c + 1).Interior.Color <> vbWhite And Cells(r, c).Borders(xlEdgeRight).LineStyle = xlLineStyleNone Then
    c = c + 1
ElseIf Cells(r - 1, c).Interior.Color <> vbWhite And Cells(r, c).Borders(xlEdgeTop).LineStyle = xlLineStyleNone Then
    r = r - 1
ElseIf Cells(r, c - 1).Interior.Color <> vbWhite And Cells(r, c).Borders(xlEdgeLeft).LineStyle = xlLineStyleNone Then
    c = c - 1
Else
    Exit Sub
End If

Call CaveMaze

End Sub

Anyway, I am curious if there is something I am missing to help make this more efficient before it overflows.

 

[6StringJazzer]

Stack overflow occurs when available memory is completely used up by the call stack. I don't think a limit of the number of levels.

Your second test is not recursive so there is no memory limit, just the limit of the size of an Integer variable. It is not relevant to your problem.

Is the code you posted all of your code? That is, if I put it into a file, will it run? Or do I need other supporting code, or a special worksheet setup?

 

[dreid1011]

Stack overflow occurs when available memory is completely used up by the call stack. I don't think a limit of the number of levels.

Yes, which is what I am trying to get around. Everything I've read says the more variables involved uses more memory. So I tried to remove the variables and write directly to the sheet.

Your second test is not recursive so there is no memory limit, just the limit of the size of an Integer variable. It is not relevant to your problem.

Which is what I was trying to achieve with the larger code by removing all the integer variables and instead of using "Call CaveMaze", I tried GoTo and a line at the top of the sub.

Is the code you posted all of your code? That is, if I put it into a file, will it run? Or do I need other supporting code, or a special worksheet setup?

Yes, that is the entirety of the code in the third segment.

 

[6StringJazzer]

I ran out of stack space at 135 levels deep, and it never popped off a level. I'm going to think about whether a redesign to do this with less memory is possible, or even whether an iterative solution is feasible. But it may take some time.

 

[6StringJazzer]

BTW I must add that I not a fan of GoTo to manage control flow. That is not causing your problem but I would rewrite this code anyway. There are other issues that make this look like an amateur job.

 

[dreid1011]

BTW I must add that I not a fan of GoTo to manage control flow. That is not causing your problem but I would rewrite this code anyway. There are other issues that make this look like an amateur job.

Understandable. I took it straight from the linked youtube video.

 

[6StringJazzer]

I downloaded the code from the web site. Did you modify the code? There are a couple of notable differences in what you posted.

 

[6StringJazzer]

The Wikipedia article gives an iterative algorithm for the same approach, I may look at implementing that if I get time

 

[dreid1011]

I downloaded the code from the web site. Did you modify the code? There are a couple of notable differences in what you posted.

I didn't download the code. I wrote it as I watched the video. The only change I can think of making is within Sub CaveMaze, I changed the "Call CaveMaze" at the bottom to "GoTo Repeat" based on some comments on the video. There were also a couple lines for a message box which I left out since he didn't end up using it in the end.

 

[dreid1011]

The Wikipedia article gives an iterative algorithm for the same approach, I may look at implementing that if I get time

I may have to take a look at the article as well. However, I had a thought last night to move Sub Backtrack into Sub CaveMaze where it was calling BackTrack, and that has made significant improvements. Instead of overflowing on a 10x20 area, I can now run it and finish 40x40.

I will continue to poke around with it though and see if I can get around the GoTo statement next.