recusive example

[MajP]

I am still not certain I understand what you are asking.
At first it was to see examples of recursion. Then it was how to sort a collection. As I said, I have never seen a sorting algorithm done recursively. I would not think that is something done with recursion. Then it was memory storage. Then purpose of calling itself (which is the whole point of recursion. So I will try to guess at your question.

1. How to write a recursive procedure.
All recursive procedure are structured the same. They have 2 things
i. They have a check to see if a condition is met. They have to have a check, to be able to "kick out".
ii. and if not then the procedure calls itself.

Public Sub RecursiveProcedure (Argument as variant)
  'maybe do something with the argument you passed in
  If not some condition then
    call recursiveProcedure optionalArgument
   ' control returns back here  
 end if
End Sub

When the procedure calls itself the first procedure "instance" is still open since It never got to the end. So if each call is given a letter it looks like this

A                   'A calls the procedure creating call B
A, B               'A and B are open control is at B
A, B, C           'A, B, C are open. Control is at C
A, B, C, D      ' D checks for a condition and it is met and it closes out. Then control returns to C.  It returns to the line after the call
A, B, C          ' C closes
A, B              ' B closes
A

2. Why is recursion needed?
If you know the amount of levels you would never need recursion. If you knew something had three levels you could simply write code like

For I = 1 to N
  For J = 1 to X
     For K = 1 to Y

But if you did not know the amount of levels you cannot do the above structure.
@moke123 example is the classic example. A folder directory is a tree structure. The first link I posted showed other common Trees and Networks (like family trees or Systems and Subsytems).
In the folder directory and these other examples you start at the top Node. If you new it only was 4 levels deep you could loop each subfoder, then each sub subfolder, then each sub sub subfolder. But you will never know that.
In the recursive call each "subfolder" checks to see if it has subfolders, and each of those checks to see if they have subfolders, ...
Eventually you get to the end of the branch. And they calls start working backwards as shown above.

3. How does the value change?
Going back to to the calls above.

Public Sub RecursiveProcedure (Argument as variant)
  'maybe do something with the argument you passed in
  If not some condition then
    argument = argument + 1
    call recursiveProcedure Argument
   ' control returns back here  
 end if
End Sub

In this pseudo code the procedure adds 1 to what is passed in.
If the condition is not met yet then all the procedure instances are open
A, B, C, D
The value of the argument in each instances is
A(1), B(2), C(3), D(4)

Normally if the condition to kick out is met you also do something at that point and return the value or pass that to another procedure.

Hopefully those are the questions you are asking.

4. Sorting using Recursion
So after Googling there are recursive Bubble Sort algorithms. If I get time I will try to write in VBA both a recursive and non recursive method. The recursive will likely be far shorter with no loops and the need to determine how many iterations before hand.

 

[conception_native_0123]

Thats what I was trying to get accross in my example using folders.

The code goes through a folder to get the name of each folder in that folder. So in RootFolder it finds a folder named Sub1A. Before the procedure moves on to find the next folder in RootFolder, it calls itself to find all the folders in Sub1A. So in Sub1A it finds Sub1B. It then calls itself again to find all the folders in Sub1B. It will do this until it no longer finds subfolders in a folder and then it returns to where it left off in the RootFolder and moves on to the next folder which in my example is Sub2A. It will continue to call itself this way until it finds no more folders.

yes works fine thank you so much! i think i may be trying to learn too much. may be i just accept that it does what it does. i do not know. i was looking to get everything i could about how it works. but in you example, you are just calling the function again and again inside itself. so may be i just accept that sorting of any collection really, happens automatically when a function calls it self. right?

i mean i wanted to see details of how it work in a picture or something. that was all. you say this

Before the procedure moves on to find the next folder in RootFolder, it calls itself to find all the folders in Sub1A. So in Sub1A it finds Sub1B. It then calls itself again to find all the folders in Sub1B. It will do this until it no longer finds subfolders in a folder and then it returns to where it left off in the RootFolder and moves on to the next folder which in my example is Sub2A

and yes i understand but for reason i am not understanding 100%. so maybe just using you example to make my own code later should be way i should do it. do you think that is right? thank you

 

[conception_native_0123]

@MajP you say this

Then purpose of calling itself (which is the whole point of recursion. So I will try to guess at your question.

i changed what i asking all the time because i was trying to learn. if definition of recursion is a function calling itself and that is it, then that is fine. i have many examples already. i guess i had 2 questions about that.

1. what happens in memory slots of computer when a function call itself?
2. why and how does recrusive function automatically sort its output?

thank you. i now will read your last reply to me.

 

[MajP]

2. why and how does recrusive function automatically sort its output?

Do you have a reference to recursion sorting its output? I assume you are referring to some example that you saw. I am not sure what you mean. A recursive procedure can be used in a sorting algorithm, but not all recursion deal with sorting. But recursion does not automatically sort things, but an algorithm can use recursion.

 

[MajP]

Here is a simple example that may illustrate. (this is just an example and would not really write code like this).
In this example you pass in a number and tell it how many times to add the number. When the procedure calls itself it passes forward how many times it has already been added and the total.

Public Sub SimpleRecursion(ValueToAdd As Integer, HowManyTimesToAdd As Integer, Optional ByVal Total As Integer = 0, Optional ByVal TimesAdded As Integer = 0)
   TimesAdded = TimesAdded + 1
   Debug.Print "Procedure has been called " & TimesAdded & " Times"
   If TimesAdded <= HowManyTimesToAdd Then
     Total = Total + ValueToAdd
     Debug.Print "Total " & Total
     SimpleRecursion ValueToAdd, HowManyTimesToAdd, Total, TimesAdded
     'Returns back to here once the called procedure closes out
     Debug.Print "Closing instance " & TimesAdded & " Total " & Total
   Else
     Debug.Print "Start Kicking out, check not met"
   End If
End Sub

Public Sub test()
  SimpleRecursion 10, 10
End Sub

I tell it to add the number 10, 10 times

Procedure has been called 1 Times
Total 10
Procedure has been called 2 Times
Total 20
Procedure has been called 3 Times
Total 30
Procedure has been called 4 Times
Total 40
Procedure has been called 5 Times
Total 50
Procedure has been called 6 Times
Total 60
Procedure has been called 7 Times
Total 70
Procedure has been called 8 Times
Total 80
Procedure has been called 9 Times
Total 90
Procedure has been called 10 Times
Total 100
Procedure has been called 11 Times
Start Kicking out check not met
Closing instance 10 Total 100
Closing instance 9 Total 90
Closing instance 8 Total 80
Closing instance 7 Total 70
Closing instance 6 Total 60
Closing instance 5 Total 50
Closing instance 4 Total 40
Closing instance 3 Total 30
Closing instance 2 Total 20
Closing instance 1 Total 10

As you can see each call pushes the total and amount of times called.
It calls it 11 times and on that time it does not pass the criteria to continue calling. That is where it begins to kick out.
You can see the line of code where it returns.
Since each instance passed the total by val and the amount of times by val they retain their original values.

 

[conception_native_0123]

A recursive procedure can be used in a sorting algorithm, but not all recursion deal with sorting. But recursion does not automatically sort things, but an algorithm can use recursion.

OK! good. that is answer i was looking for. that is wonderful! so, I think example I saw years ago used recursion inside sorting algorithm. actually i might be able to find it. let me look.

 

[conception_native_0123]

yes i see it. i found it. these are 3 functions i saw a long time ago. and it must be some sort of sort or something

Public Sub RunMix()
    Call mixTest("testValue")
End Sub

Public Sub mixTest(ByVal sInput As String)

Dim aString() As String
Dim X As Long

aString = mixString(sInput)

For X = 0 To UBound(aString)
    Cells(CurrentRow, 1) = aString(X)
        CurrentRow = CurrentRow + 1
Next X

End Sub

Public Function mixString(ByVal sInput As String) As String()

Dim aPos() As Long
Dim aString() As String
Dim lCounter As Long
Dim X As Long, Y As Long

ReDim aPos(1 To Len(sInput))

Do
    aPos(1) = aPos(1) + 1
    For X = 1 To Len(sInput) - 1
        If aPos(X) > Len(sInput) Then
            aPos(X) = 1
            aPos(X + 1) = aPos(X + 1) + 1
        End If
    Next X
    If aPos(Len(sInput)) > Len(sInput) Then Exit Do
    For X = Len(sInput) To 2 Step -1
        If aPos(X) > 0 Then
            For Y = 1 To X - 1
                If aPos(X) = aPos(Y) Then GoTo Continue
            Next Y
        End If
    Next X
    ReDim Preserve aString(lCounter)
    For X = Len(sInput) To 1 Step -1
        If aPos(X) > 0 Then
            aString(lCounter) = aString(lCounter) & Mid(sInput, aPos(X), 1)
        End If
    Next X
    lCounter = lCounter + 1
Continue:
Loop

mixString = aString

End Function

 

[MajP]

That is a sorting algorithm, but it is not recursive. If it was recursive then MixString would call itself. It never does that. It just uses a do loop with internal loops.

 

[conception_native_0123]

ok thank you. i see that yes.

 

[The_Doc_Man]

@conception_native_0123 - you asked (more or less) WHY one would use recursion, under what circumstances. I can try to answer this one and I hope it is less contentious than that other thread.

I got involved with the Ancestry.COM site because I was building a family tree for my grandsons. In this case, I had to do some complex parsing of the data downloaded from the Ancestry site. Once I built the data structure, I was able to fill in slots in my database for each person. But then, to actually be able to present what I had downloaded, I had to write a recursive routine to find parents, then grandparents, then great-grandparents, etc. for placement on an "ancestor's tree." AND when looking at the offspring of one particular couple, I needed to be able to find their children, grandchildren, great-grandchildren, etc. on a "descendant's tree."

It might be possible to imagine (as MajP has pointed out) that if you knew how many generations were involved, you could just write code that looked specifically and only for 3 generations in either direction. However, in my studies with Ancestry data, I have gone back a variable number of generations dependent on availability of birth records. In two cases I took my family tree back to Essex, England and Gloucestershire, England and I took my wife's family tree back to Acadia, Nova Scotia and (in another branch) to the Grand Canary Islands. I think the longest chain of ancestry I found was 10 generations back.

Therefore, just like computer file directory structures which work best with recursion, ancestry data also is recursion-oriented.

In a separate post I will try to explain another of your questions in this thread, the one about "what happens in memory."

 

[The_Doc_Man]

1. what happens in memory slots of computer when a function call itself?

This is from your post #23. I will try to not confuse you, but it is a complex subject.

Let's agree on a definition here. When you have ANY routine to be called, then while that routine is active, you have an INSTANCE of that routine. I will use the term INSTANCE in this discussion. Let's also understand that the answer to your question relates to the program stack. I will not try to discuss that here too much. However, it IS a topic you can easily research online.

When you call ANY subroutine or function, VBA builds a "call context" on the program stack. This context is really just a big chunk of memory on the stack. In it you have various information to support Access management actions on the menu bar that appears in the VBA code windows; actions like "View Call Stack" as the biggest example. The error-reporting code within Access also uses this context.

This call context contains the information necessary for VBA to allow you to return to your caller and pick up where you left off in the calling routine when the called routine is done. Another part of the context is the suppliled argument list.. A third part is the local variables list - anything you declared local to that routine. I.e. any DIM statements.

In ANY called routine, these local variables act like named temporary variables. They have legitimate addresses in memory so the routine's compiled instructions can reference those addresses. BUT ... when the subroutine exits, it "dissolves" the context area, so ALL locally declared variables cease to exist. Once you leave the routine, if you had somehow trapped and externally stored the address of one of those variables, it would no longer be valid and its contents in physical memory, if still accessible, could not be trusted to be meaningful.

The routine's "formal" parameters are also in this class of temporary things. If your call declaration named them as X and Y, they have legit addresses in the call context, but when that gets dissolved, they go away too.

In recursion, all that really happens is that VBA creates a new call context for the new instance of that recursion routine. So here is where you might be confused. If you declared a variable called X in the routine, and a recursion occurred, there are now TWO copies of X, one in this routine and the other in the previous iteration, right? But only one call context is ever CURRENT and you cannot see what is in other contexts. So only the local variables of the currently active instance of the routine can be seen. The local variables of other (stacked) instances are not visible.

It is in this context discussion that the other thread (about ByVal/ByRef call arguments) becomes significant. In some cases, you want the recursive routine to modify what will be seen by other routines. This is where a ByRef becomes important. If you use a ByRef argument, which is in essence a pointer to the real variable, you modify the real variable. If you use a ByVal argument, then you are working on a local-context COPY of the real variable. Anything you do to that local-context copy is forgotten when the current instance of that routine returns to its caller, because the local copies were in the call context area and they get dissolved, returned back to the computer for later re-use. Confusion occurs here when the ByVal argument is an object. Basically, don't deal with ByVal of objects. Design it some other way.

I hope this call context discussion doesn't confuse you too much. I can answer ONE MORE implied question... HOW does the computer keep all of the local variables for each call instance separate? Because PCs are based on a machine that has something called relative-register addressing (a.k.a. register-offset). The call context is on the stack so the variables for the current local context are available unequivocally through register-offset addresses. The "deeper" instances are still on the stack, but with different offsets relative to the current value of the stack pointer register.

 

[conception_native_0123]

thanks you doc man. i have to read that few times to make sure i understand. i will post more if I cannot understand. thank you all.

 

[The_Doc_Man]

No problem. And I understand it is a lot to contemplate. But it is important to understand the concept of a call context. NOTE: I remember now that in SOME references, that chunk of memory put on the stack during the call preparation step is also called a Call Frame.

 

[The_Doc_Man]

As a follow-up, I found an article with diagrams. The pictures should clarify what I told you, which was more or less exactly right except perhaps for the order in which each element appears on the stack.

Breaking Down the Call Stack

Stack Background

medium.com

This shows you more or less what happens in non-trivial call stack environments.

 

[conception_native_0123]

that article good doc man. but i find it funny that it contains this

But WHAT THE HELL is a stack?

ha ha ha. i learned a lot from reading it. thank you so much.

 

[The_Doc_Man]

Happy to help.