Sometimes I have two options for solving a problem - I can do it recursively or iteratively. I know that recursive can often be faster for smaller operations, whilst iteration starts to get faster as the number of times your have to repeat an operation increases. . To test this, I used the code found here to create a timer class, cTimer, and recorded how long it took to complete reversing a string with two different functions - one which was iterative, the other recursive: basically I wanted to find out at what point I should switch from using an iterative to a recursive function if I know, for instance, that I could choose between iteratively or recursively reversing a string str, and that Len(str) is likely to be >40.
Sub TimeReverse()
Dim strA As String, tStamp As cTimer, i As Long
strA = ""
For i = 1 To 1000
strA = strA + RandomChar
Sheets(1).Range("a1").Offset(i, 0).Value = i
Set tStamp = New cTimer
Call tStamp.StartCounter
Call InvertString(strA)
Sheets(1).Range("b1").Offset(i, 0).Value = CStr(tStamp.TimeElapsed)
Set tStamp = Nothing
Set tStamp = New cTimer
Call tStamp.StartCounter
Call ReverseString(strA)
Sheets(1).Range("C1").Offset(i, 0).Value = CStr(tStamp.TimeElapsed)
Set tStamp = Nothing
Sheets(1).Range("e1").Offset(i, 0).Value = "=SUM(C" & i + 1 & "-C2)"
Next i
End Sub
Public Function InvertString(str As String) As String
Dim str1, str2, str3, midChar As String, i, x, z As Long
If Len(str) Mod 2 = 0 Then
str3 = " "
x = 1
For i = 1 To (Len(str) / 2)
str1 = Mid(str, i, 1)
str2 = Mid(str, (Len(str) - (i - 1)), 1)
str3 = Mid(str3, 1, x) & str2 & str1 & Mid(str3, (Len(str3) - (x - 1)), x)
x = x + 1
Next i
InvertString = str3
Else
z = (Int(Len(str) / 2) + 1)
midChar = Mid(str, z, 1)
str3 = " "
x = 1
For i = 1 To (Len(str) / 2)
str1 = Mid(str, i, 1)
str2 = Mid(str, (Len(str) - (i - 1)), 1)
str3 = Mid(str3, 1, x) & str2 & str1 & Mid(str3, (Len(str3) - (x - 1)), x)
x = x + 1
Next i
InvertString = Mid(str3, 1, z) & midChar & Mid(str3, (z + 1), z)
End If
End Function
Public Function ReverseString(ByVal str As String) As String
'Recursively reverse a string
If Len(str) <= 1 Then
ReverseString = str
Else
ReverseString = ReverseString(Mid(str, 2, Len(str))) + Mid(str, 1, 1)
End If
End Function
Private Function RandomChar() As String
Dim b As Integer, t As Integer
b = 32
t = 126
RandomChar = Chr(Int((t + 1 - b) * Rnd + b))
End Function
I understand that these functions may not be the fastest way to complete the task - and, of course, there is a built in reverse string operator in VBA (which I chose not to use because I wanted to understand the structure of the functions I was comparing)
I converted the output into a chart:
What I want to ask is "what explains the sharp spikes for some function calls?" It looks like sometimes the spikes seem to occur in both the recursive and iterative procedures for the same string, but (on the left hand side at least) the spike is usually noticeably smaller in the iterative line (although I must admit I haven't checked to see if the proportional difference from base is the same for both lines). But sometimes they are not aligned at all. Is it that some characters are harder to process, or that some background activity is delaying the function (which would explains shared peaks I guess), and, if it is background activity, how come the spikes are not pretty much always aligned? For instance, towards the right hand-side of the chart, there are some pretty massive spikes in the iterative process that don't seem to be shared by the recursive to nearly the same extent. Is it because these functions are now running for so long that background activity has a greater variation in effect upon the two functions in that test loop? What I'm particularly interested in is whether it's something to do with the way I have written these functions? How can I work out from this sort of data how I can smooth out and improve the operation of my functions? Or do I need to rethink how/the purpose for which I gather my data?
