When does recursion limit bite you?

Ben Rubinstein benr_mc at cogapp.com
Tue Oct 4 13:33:31 EDT 2011


On 04/10/2011 15:54, stephen barncard wrote:
> Another question is  - is there another, non-recursive way to walk all
> folders? Some kind of two-pass method? Or is this just the way it is?


My standard non-recursive file walker looks something like this, given tRoot 
as the path to the folder you're starting from:

   put return into tFoldersToDo
   repeat until tFoldersToDo = empty
     put line 1 of tFoldersToDo into tSubPath
     delete line 1 of tFoldersToDo
     set the defaultFolder to tRoot & tSubPath
     --
     if bDoRecurse then
       repeat for each line f in the folders
         if first char of f = "." then next repeat
         put tSubPath & "/" & f & return after tFoldersToDo
       end repeat
     end if
     --
     repeat for each line f in the files
       doSomethingToFile f
       -- NB full path to file: tRoot & tSubPath & "/" & f
     end repeat
   end repeat


As to whether this is any less likely to choke than a recursive solution... 
that depends partly on the shape of your file tree.  This approach deals with 
the files in each folder at the same time as it examines it for sub-folders, 
so it doesn't necessarily build up a huge list of folders before it starts 
working through them; but the same is true of a recursive solution.

As written, it's approximately breadth-first; it deals with all the folders at 
level 1, piling up a list of the folders in level 2; then it deals with all 
the folders in level 2, piling up a list of the folders in level 3.

If you change 'after' to 'before' in the line
     put tSubPath & "/" & f & return after tFoldersToDo

then it will go depth first; piling up a list of the folders in the root, then 
diving down into the first one, recording its subfolders and diving into the 
first, etc.  For some shapes of file tree that might work better.

Ben




More information about the use-livecode mailing list