Understanding Recursion

Hi Everyone, I have always struggled with the idea of recursive loops and hierachical istBox lists and was wondering if anyone knows of any good tutorials or examples of how to process lists where you hold a parent id in a database along with each row. It is one of those things that I have tried to learn so many times over the years and it never seems to stick as to the process of adding things to the list and the order in which you do it etc. I believe their are different ways to do for optimal speed etc top down, bottom up parsing of the data etc but I have not even grasped the basic simple way yet and any pointers to where I might find something to help would be really appreciated. Thanks

Technically you shouldn’t need recursion for a listbox. If you store the row id in the rowtag property, just implement the Expanded event so that it retrieves all rows whose parent id = rowtag of the row that was expanded and then just use addrow to add them.

To define recursion, you must first define recursion.


Thanks Greg I did not know you could do that with a listbox.

Gavin, sorry I should have been clearer.

I guess the easiest example is the filing system where you have folders and files and sub-folders and more files going many levels down. What I want to do is understand how you create a tree visually and then walk thought it. I can see that using wha Greg has said that you can spoof the effect of the tree which is something I do want to do but I also want to understand how you can build a tree from a root down where you have many children and subordinates or nodes etc.

One technique I have used recently, which may be relevant

Database -> table
Fields: MyRef, MyText, ParentRef

(This is the bare minimum information needed for org charting software such as Org Plus or Visio. Ideally there would be an ID field too, but we dont need to look at that for the example)

Sample data:

A00,The World,Nil A01,USA,A00 A02,China,A00 A03,Spain,A00 A04,Texas,A01 A05,Florida,A01 A06,Hong Kong,A02

To display as a nested list, (this is only pseudo code)

Start by selecting rows which have NIL as a parent (there should be one)

You get: The World.
Add that to a listbox, and stick the Reference into the rowtag.

Now, someone expands the row that shows ‘The World’

In the Expanded event, go back to the database and

Select  * from theTable where ParentRef =   <rowtag value>

Add child rows to ‘TheWorld’, and set their rowtags to be their own refs.

And thats basically it.

You can fill the list (completely expand it) by looping repeatedly through the list, and expanding any unexpanded row, until the number of expanded items on ‘this pass’ was zero.

There are custom listbox controls that emulate a treeview and allow the entry to the “tree” as simple parent,child relations
one of which is

Thanks Jeff, that is a nice way of doing it and is probably what I will do for the project I am working on but I am also looking to “learn” how to handle recursion myself to learn how to be able to walk though a list with many children and subordinates etc.

Dave: thanks, I did purchase your plugin for another project and it works (although a little slow at time with many nodes >3000) but this time round I am trying to learn how to do it myself as it has been one of those things that over the years I have struggled getting my head around so thought it was about time that I make the effort to learn the methodology or technique that is used. Thanks

The thing about recursive procedures is knowing when to stop
Here is a simple example that creates longer and longer strings until the string is 6 characters in length, then winds backwards

call MyRecurs (“A”)

Sub MyRecurs( V as string)
dim locstr as string
if len(v) < 6 then
locstr = V + “X”
msgbox locstr
call MyRecurs ( locstr)
end if
end sub[/code]

Folders and Files:
You can imagine a scenario where what is passed in, is a folder
if the folder has children, list them.
If any of the children is a folder, call the routine again.

Thanks Jeff, you have just hit the nail on the head and the bit that has alluded me for so long. It is the “knowing when to stop” and the method that is calling itself, I just could not get my head around that in the past. Thank you thank you thank you, this has been one of those things that has confused me for the past 30 years, dont ask me why because I couldnt tell you, just has. Wow I am so happy to be able to tick that one off the list. Cheers I owe you a pint if you ever get to Jersey (not too far from the Midlands, just keep going south beyond Southampton and if you reach France walk about about 14 miles and the pint will be waiting for you :wink:

Here is another example:

[code]Private Sub GetListOfMails(StartFolderitem as FolderItem)

'generate the list by going recursive starting with StartFolderitem

if StartFolderitem = nil then return

dim theFileList as new FileListMBS(StartFolderitem)
dim FileCount as Integer = theFileList.Count - 1
for currentFile as Integer = 0 to FileCount

if theFileList.Visible(currentFile) then
  if theFileList.Directory(currentFile) then
    ListOfMails.Append theFileList.TrueItem(currentFile)
    GetListOfMails theFileList.TrueItem(currentFile)
    ListOfMails.Append theFileList.TrueItem(currentFile)
  end if
end if


End Sub[/code]

The trick is to call the function again when you have a directory and add the file to the result if it’s not a directory.

Thanks Beatrix that is really helpful and the sort of thing I am going to write.

That sort of thing is one of the easier ones to rewrite to not be recursive.
And it gives you much better control over how large the stack gets (which recursive versions often dont)
And in this case it doesn’t require a module level property to collect the results
It’s all locals

Dim theFileList() As folderitem

If StartFolderitem = Nil Then Return theFileList

 // create the initial list of things to examine which is all the visible items in startFolder
For currentFile As Integer = 1 To StartFolderitem.Count
  If StartFolderitem.TrueItem(currentFile).Visible Then
    theFileList.append StartFolderitem.TrueItem(currentFile)
  End If

// now work our way through the list and add any items to it we have no already dealt with that are visible
// so yes the list grows as we go
For currentFile As Integer = 0 To theFileList.ubound
  If theFileList(currentFile).Directory Then
    // add the visible items of this dir to our list of items to examine
    For i As Integer = 1 To theFileList(currentFile).Count
      If theFileList(currentFile).TrueItem(i).Visible Then
        theFileList.append theFileList(currentFile).TrueItem(i)
      End If
  End If

// and now we've worked our way through the list and we can give back the list 
Return theFileList

Thanks Norman, that is an interesting way to do. I have learnt a lot today from everyone. Thank you all for your comments and help, especially on the weekend.

I think there’s some theorem that shows that you can turn any recursive algorithm into an iterative one (and vice versa)
Something to notice from the recursive vs iterative one is that in the recursive one you get a “stack” because each new method call creates a new set of locals etc.
In the iterative versions you end up managing that stack yourself.

Wikipedia has some interesting comments on the recursive vs iterative approaches
And since Xojo is an imperative language I would suspect that the non-recursive versions would perform slightly better becuase they avoid extra calls etc

[quote=331789:@Dave S]There are custom listbox controls that emulate a treeview and allow the entry to the “tree” as simple parent,child relations
one of which is
@Dave S : So your treeview is based on the standard listbox? Or is it based on canvas?
Can it be ported to the Web, for use with the Xojo WE?

[quote=338917:@Oliver Osswald]@Dave S : So your treeview is based on the standard listbox? Or is it based on canvas?
Can it be ported to the Web, for use with the Xojo WE?[/quote]
It is based on a listbox… and “should” be WE compatible, but I have never tried, and have no resources to do so

I understand, thanks Dave!