Recursive Functions, How to Create

[raskew]

Hi -

I've just started playing with recursive fuctions, and admittedly I'm struggling just a tad.

Here's a non-recursive function I wrote to remove unwanted characters from a string.

Anyone up to a challenge of rewriting this as a recursive function:

Public Function fFixWords3(pStr As String) As String
'------------------------------------------------------------------
' Purpose:   Remove non-Alpha/non-numerical characters from a string
' Coded by:  raskew
' Arguments: pStr: The string to be searched.
' Input: from debug (immediate) window
'              ? fFixWords3("132$/8 AS-01-HO1 ")
' Output:      1328AS01HO1
'------------------------------------------------------------------
Dim strHold As String
Dim strKeep As String
Dim chrHold As String
Dim intLen As Integer
Dim n As Integer

    strHold = Trim(pStr)
    intLen = Len(strHold)
    For n = 1 To intLen
       chrHold = UCase(Left(strHold, 1))
      'the following accepts (A - Z) and/or (0 - 9), exclusively
       If Asc(chrHold) >= 65 And Asc(chrHold) <= 90 Or Asc(chrHold) >= 48 And Asc(chrHold) <= 57 Then
          strKeep = strKeep & chrHold
       End If
       strHold = Mid(strHold, 2)
    Next n
    fFixWords3 = strKeep

End Function

It works spiffy as written, but I played with it (and bombed) trying to convert it as a recursive function.

There's no desperation in my request--no 'I have to turn this in my 09:00 tomorrow', just a desire to see how it might work.

Any suggestions greatly appreciated.

Best wishes - Bob

 

[Banana]

It took me a while to think it through because TQBH, it's not of case where I would think recursive functions would be a better solution (and I've not really find case it was truly needed that loop control couldn't accomodate)

Nonetheless, here's a prototype:

Public Function fFixWords3(pStr As String) As String

Dim char As String


If pStr = "" Then
    fFixWords3 = pStr
Else
    char = UCase(Left(pStr, 1))
    Select Case Asc(char)
        Case 48 To 57, 65 To 90
            fFixWords3 = char & fFixWords3(Right(pStr, Len(pStr) - 1))
        Case Else
            fFixWords3 = fFixWords3(Right(pStr, Len(pStr) - 1))
    End Select
End If

End Function

It was a bit unusual because it's not usual problem where I think that recursive function is the best solution, especially with passing the Right(pstr, Len(pstr) -1) several time which seems to me quite inefficient compared to the loop.

Here's a example where recursive functions may make more sense (to me at least):

Public Function StripTrailingNumbers(sInput As String) As String

If IsNumeric(Right(sInput, 1)) Then
    sInput = Left(sInput, Len(sInput) - 1)
    sInput = StripTrailingNumbers(sInput)
End If

StripTrailingNumbers = sInput

End Function

But that function could easily be written as:

Public Function StripTrailingNumbers(sInput As String) As String

Do Until IsNumeric(Right(sInput, 1))
    sInput = Left(sInput, Len(sInput) - 1)
Loop

StripTrailingNumbers = sInput

End Function

Not only that it's faster and efficient to do a loop instead of recursive function, I've had difficulty coming up with a recursive function that a loop control couldn't perform just as well and for that reason haven't made use of it.

 

[raskew]

Banana -

Thanks, I do appreciate you!

I'll play with these. It was never my intent to say that a
recursive solution was the (best, fastest) solution.

Conversely, my eyes tend to cross when I look at a 'recursive
solution' and I have a real problem following the logic. i was
just loooking for an example that I could compare against my
non-recursive solution and maybe make some sense of it.

This you've provided and I appreciate your effort.

Thanks again - Bob

 

[Banana]

I suspected that it was the case that you just wanted to play with some examples. My commentary was more of musing if there ever could be a case made for recursive functions and if there is, I'd love to know about it. Nonetheless, it's always good to add new tools to the toolbox.

WRT building them, I think the stumbling block is to make the mistake of starting with the input and trying to run it through. It's easier to work it out if we start with the "last call" of the function and work backward, then the logic needed to perform should become a bit more clearer. (At least that's what worked for me)

So with your function, I had to figure how I would "iterate" over the whole string, and in that case, I did by trimming the string one character at a time while the function itself looks at the first character of any string it is given. So in the last call, the pStr would be now "", which returns "". Taking us back one level down, we get the last character, and if it's a good character, concatenate it, or don't.

So, the stack call from the last call and unwinding back to the first call would look like this-

Output:
""
1 & ""
0 & 1
H & 01
1 & H01
...
1328AS01HO1

So in that case, thinking it out in reverse was what clicked for me.

 

[gemma-the-husky]

bob

naturally recursive structures lend themselves to recursive alogrithms. This is why xml structures (which are defined recursively) are easily iterated with recursion

tree walking in general (xml files being a specific example) is a real important use of recursion - its elegant and simple in a way that sequential code could never be.

given a node with children, each of which can have children then you can iterate the tree as follows, given an entity of type node, with this very simple code fragment (not vba, but similar to the code in the DOM document model. One problem with stuff like this is it needs a pointer type, which is not avaialble in vba.

note that the code to process the node (processnode) can be placed before the recursion or after - every node is still visited, but the order of processing the nodes changes.

'recursive tree walker

sub main
traversetree(root)
end sub

sub traversetree(thisnode as node)
processnode 'doesn't have to be placed here - this could be placed after the next statement
if thisnode.haschildren then
   for each child
       traversetree(thisnode.child)
   next
end if
end sub

----------
a common example of recursion is the fibonacci series - since any number is the sum of the previous 2 numbers then you can say the following, and this is vba code.
Again this is simple to code with recursion, but much trickier without.

note that recursion works by pushing and popping values off the stack, and therefore relatively low values of this fibonacci series will take increasingly long to process (try it) - and may actually exhaust the stack space.

'recursive code to extract fibonacci numbers

sub main
msgbox("12th fibonacci number is " & fib(12))  'determine the value of the 12th fibonacci number
end sub

sub fib(x as integer)
if x=0 or x=1 then 
   fib =1 
else
   fib = fib(x-1)+fib(x-2)
end if
end sub

------------

unfortunately the dir function in vba is a non recursive function (ie the data structure is not pushed onto the stack) - as otherwise it would be very easy to examine a disk file structure recursively using the dir function.


you can write the fibonacci series code without recusrion failrly easily, but tree walking without recursion is really really diffcult.


hope this helps

 

[jardiamj]

When I saw this post I thought in XML file structure as well, but I avoided to post cause I was not sure if it can be done other way than using recursive functions. I am working with XML files but using PHP, it should be the same just other language.
I'm using the XML files to store information about plants for a website, I didn't want to store that information in the MySQL database because every plant can have different information particularly related to it, so my db would become in a bunch of fields where some would be filled just for one plant and empty for all the rest of them.
With the XML files I can just store the information with any tags I want, and give them attributes. And easily walk through all the tree structure getting the information.
But I had to create also an application to allow people to create and edit the files, without having to mess with the files themselves.
I know it might be out of the scope of this post but I would like to hear if some one has another suggestion for this kind of things, without using XML Files.
Thanks. Cheers!

 

[Banana]

A very interesting approach, jardiamj. I would have never thought of using XML files.

(I have to confess that I have a bit of bad taste with XML files; there's no guarantee that one XML file written by one source will be readable by the destination, unless the there's a meaning of specifying format, which to me sounds more work than it ought but that's just me or maybe I just didn't get it. Would love to learn more, though)

But in regards to your question about doing this without a XML file- I know there is a data model called Entity-Attribute-Value model, which basically does what you described. It's usually popular in medical application because doctors may have 1,000s of questions they may want to ask patients, but several of those questions do not apply or apply only to a specific answer of a "parent" question. To easily record all applicable answers to various questions, the users would select the question from "Attribute" group, associate with a patient ("Entity") and enter the answer ("Value") to it. The database then look up all related question via Attributes/Values group and return the list of relevant questions to which users then fill out.

Here's a wiki about this.

Of course, the model has its problems and drawbacks and usually only make more sense when you have a large number of things you *may* want to know about something but for 90% of time they don't apply, and you want to be able to maintain the list of questions to ask comparatively easily without hassle of managing a deep tree of child tables.

 

[Thinh]

The only place that I that used a recursive function in life is with Bill of Materials.

Master Part Table
ID, Parent ID, PartNr, Quantity
1,0, PART A, 2
2,1, PART B, 1
3,2, PART C, 1

Recursive functions works great with Bills of Materials as it allow you unlimited levels of bills of materials.

 

[jardiamj]

Thanks Banana, for that interesting data model you brought to me. I gave it a brief look, but I will read it more carefully, if my girlfriend allows me to do so... lol.
I stick with the XML Files for now, they work fine for me. But I will document myself on the model you wrote about.
Thanks again!
Cheers!