IBM®
Skip to main content
    Country/region select      Terms of use
 
 
   
     Home      Products      Services & solutions      Support & downloads      My account     

developerWorks  >  Lotus  >  Forums & community  >  Best Practice Makes Perfect

Best Practice Makes Perfect

A collaboration with Domino developers about how to do it and how to get it right in Domino

Bob Balaban recently posted about recursion and how to program so that it is not needed. The main problem is that the size of the LotusScript stack is limited, and bad things happen if you exceed it. This is generally not a problem if you're not using recursion, because the stack only goes as deep as you have explicitly designed it to go.

I agree that it's better to try for an iterative implementation in many cases. I just thought Bob's example was rather long and complex, and I happened to have a simpler one that makes the point more clearly, and is useful. The problem was to write a function like the Mkdir command, but that would work even if the containing directory didn't already exist. So for instance, you would use the call:

MakeDir "C:\movies\stars\carmen-miranda\pics"

If you do this with the built-in Mkdir function, it will fail if the containing folder (C:\movies\stars\carmen-miranda) doesn't already exist. I wanted it to be able to create the whole series of folders, if necessary.

The simplest way to find out whether the containing folder is already there, is to try a Mkdir of the whole path and trap the error that happens if it is not so. Yes, you could parse out the filepath and explicitly check for the existence of the parent and whether it's a directory, but why do all that work when the Mkdir command will do it for you? So here's a recursive and iterative implementation of the task using that technique:

Recursive MakeDirR Iterative MakeDir
Sub MakeDirR(Byval strWhere$)
      On Error 76 Goto parentDoesNotExist

      Mkdir strWhere

      Exit Sub

parentDoesNotExist:
' or other problem, but let's assume that for now.
      On Error 76 Goto fullpatherr

      Dim fname$, fpath$

     
SplitFilepath strWhere, fpath, fname
      MakeDirR fpath

      Mkdir strWhere

      Exit Sub
End Sub
Sub MakeDir(Byval strWhere$)    
       On Error 76 Goto parentDoesNotExist

       Dim stack$

       Const NL = {

}

       Do

               Mkdir strWhere

               On Error Goto 0
' first success, stop trapping errors; avoid infinite loop.
               strWhere = Strleft(stack, NL)
' "pop" a path for next iteration
               stack = Mid$(stack, Len(strWhere)+2)

failed:

       Loop Until strWhere = ""

       Exit Sub

       
parentDoesNotExist:

       ' This error code can indicate other problems, but assume missing parent.

       ' If not, we get a different error (75) later when trying to create the parent.

       Dim fpath$, fname$

       
SplitFilepath strWhere, fpath, fname
       If fpath = "" Then Error 76, "Invalid path: '" & strWhere & "'"

       stack = strWhere & NL & stack
' "push" onto stack to retry later.
       strWhere = fpath
' try a path one step shorter.
       Resume failed

End Sub
Code shared by both approaches:
Sub SplitFilepath(Byval fullpath$, dirpath$, filename$)
       Const DELIMS = {/\:}

       While Instr(DELIMS, Right$(fullPath, 1))
' discard final delimiter character...
               fullpath = Left$(fullpath, Len(fullpath)-1)

       Wend

       Dim candidate$, i%

       filename = Strtoken(fullpath, Left$(DELIMS, 1), -1)

       For i = 2 To Len(DELIMS)

               candidate = Strtoken(fullpath, Mid$(DELIMS, i, 1), -1)

               If Len(candidate) < Len(filename) Then

                       filename = candidate

               End If

       Next

       Dim fplen%

       fplen = Len(fullpath)-Len(filename)
       If fplen > 0 Then fplen = fplen - 1
       dirpath = Left$(fullpath, fplen)

End Sub


Look at the recursive routine, MakeDirR, first. The role of the stack here is to keep track of the remaining work to be done, and where in the middle of a suspended task we were (on which line). This routine tries to create a folder, and if this fails, tries to create the parent folder, and if that fails, tries to create its parent folder, and so on until either the create succeeds, or there's an error that's not consistent with a missing parent folder. Then it backtracks to create the folders that it put off creating earlier (this time not trapping errors, to avoid infinite recursion). The variable strWhere has a different value at each level of the stack, and that's how we remember what folder we were trying to create at that level.

Converting any recursive implementation to iterative, requires a replacement for the role of the stack in tracking work to be done. In Bob's example, he uses a Queue class. This is a good way to do it, and it's nice to have such a class in your personal library (I have a version that's not specific to DOM nodes). But it doesn't need to be that complex; in many cases an array or string can be used to stuff everything you want to keep track of. The nice thing about a string or a "redimmed" array, is that it doesn't take up a lot of room on the stack -- just a few bytes -- but you can store lots of data in it. This is also true of an object variable.

In my example, I use a string (stack) to keep a list of the directories I must try to create. This technique depends on the existence of a delimiter character (newline in this case) that will not appear in the data. Each time creation of a folder fails, the failed path is added to the beginning of stack, and the last part of the path is dropped. Again, once successful in creating a folder, it turns off error trapping to avoid an infinite loop. This is the same sequence of operations as the recursive function, but without the stack, we have to add logic to explicitly store and retrieve information and to control position in the code. This makes the iterative implementation a little longer, as usual (though in this case some of the extra length is caused by better comments).

So the iterative implementation has a little more code, and lacks the elegant simplicity of recursion, but is safer (and often more efficient). In this case, the chance of overrunning the stack limit is probably fairly small, since a path won't have so very many levels of folder names. We'd probably be just fine with the recursive approach, unless we're already pushing the limit before we call this routine. So, do what you think best -- but I'm putting the iterative version in my library.

Andre Guirard | 11 April 2008 05:12:00 AM ET | Home, Plymouth, MN, USA | Comments (1)


 Comments

1) Recursive Mkdir (vs. Iteration)
Rock | 4/11/2008 1:59:20 PM

I know you did this example to be practical and also illustrate your points of recursion vs iteration, but I wanted to let everyone know that there is a much simpler way to accomplish this task - as long as you're using Windows.

There is a Win API method called MakeSureDirectoryPathExists. I have documented how to use this function (plus another function as well) in the following blog entry:

{ Link }

Enjoy!

--Rock

2) Recursive Mkdir (vs. Iteration)
Andre Guirard | 4/11/2008 4:23:40 PM

Yeah, well... who wants to use Windows?

3) Recursive Mkdir (vs. Iteration)
harkpabst meliantrop | 4/14/2008 2:46:36 AM

If it was just for Win, one would even get away with a shelled out Windows mkdir (which can create the complete hierarchy in one go), followed by some loop to check, if the target folder has already been created.

But as you said, who wants to use Windows ...

4) Recursive Mkdir (vs. Iteration)
Charles Robinson | 4/14/2008 8:57:06 AM

Only about 90% of companies. If there truly was commercial interest someone would create a cross-platform framework that is able to thunk down to the OS operations. Java doesn't get there, so I wonder who will do it first?

5) Recursive Mkdir (vs. Iteration)
harkpabst meliantrop | 4/15/2008 2:58:24 AM

Charles, I'd love to see some figures comparing the number of Domino users supported on Windows servers vs. the other operating systems (and in particular Linux, of course). Since betting a beer is cheap on the Internet, I'd bet you, that it's less then 90% on Windows ...

6) Recursive Mkdir (vs. Iteration)
Kerr | 4/15/2008 5:39:55 AM

Well, for generating directories, Java's java.io.File.mkdirs() will do the job.

7) Recursive Mkdir (vs. Iteration)
Charles Robinson | 4/15/2008 9:02:13 AM

Harkpabst, that's a rather convoluted logic path. The question asked was "who wants to use Windows", not "how many Domino users are supported on Windows servers." Windows has about 92% of the desktop and roughly 60% of the server market. That tells me a whole lot of people use Windows.

If you're coming to ILUG or Lotusphere I'll buy you a beer and we'll call it even. :-)

8) Recursive Mkdir (vs. Iteration)
Scott Leis | 4/15/2008 8:32:51 PM

Regarding the Windows API calls, the Dir function in LotusScript can check for the existence of a directory. This allows the MakeDir function to be written without the "parentDoesNotExist" error trap, but also avoids use of the Windows API.

A recursion vs iteration problem I had a few years ago was sorting an array of a few thousand documents based on field values. Recursive quicksort consistently failed. A Google search quickly found some VB code for an iterative shellsort, which worked well in LS.

9) Recursive Mkdir (vs. Iteration)
harkpabst meliantrop | 4/16/2008 2:55:24 AM

Well Charles, isn't convoluted logic exactly what is required to understand recursion? ;-) Whoever said: "To understand recursion, you either have to know someone who can explain it to you, or you must have understood it before."

And no, I'm not going to start a discussion now, if "92% do use Windows" means 92% want to use Windows ... ;-)

10) Recursive Mkdir (vs. Iteration)
Andre Guirard | 4/16/2008 3:52:11 PM

Scott, yes, you can write the code without an error trap, but I don't want to. They're a normal part of coding as far as I'm concerned, and if the code is simpler with them (and faster) why not use them?

 Add a Comment
Subject:
   
Name:
Comment:  (No HTML - Links will be converted if prefixed http://)
 
Remember Me?     Cancel

Search this blog 

Disclaimer 

    About IBM Privacy Contact