Topic: Recursion.. not really right now but trying.

[T.Willey]

I'm sure this can be written to be recursive, but I can't figure it out right now.  I have looked at this for two days, and can't seem to grip what I should do.  I have it in a while loop, but I was trying to see if it can be done in a recursive way.  Here is my code.  It grabs all the sub directories from a staring directory.

Code: [Select]

(defun AllSubDirs (Main / DirList cnt Index tmpList FindSubDir)
; Returns a sorted list of all the directories found under the one supplied.

;--------------------------------------------------------------
(defun FindSubDir (Path / )

(mapcar
 '(lambda (x)
  (strcat Path x "\\")
 )
 (vl-remove-if
  '(lambda (y)
   (vl-position y '("." ".."))
  )
  (vl-directory-files Path "*" -1)
 )
)
)
;----------------------------------------------------------------------
(setq DirList (list Main))
(setq cnt 1)
(while (>= (setq Index (- (length DirList) cnt)) 0)
(setq tmpList (FindSubDir (nth Index DirList)))
 (foreach i tmpList
  (setq DirList (cons i DirList))
 )
 (setq cnt (1+ cnt))
)
(vl-sort DirList '(lambda (a b) (< (strcase a) (strcase b))))
)

Any help is appreciated.

[Jürg Menzi]

Hi Tim

That's what I use:

Code: [Select]

;
; == Function MeGetSubFolders
; Returns a recursive list of all folders behind a start folder.
; Arguments [Type]:
;   Fld = Start folder [STR]
; Return [Type]:
;   > List of all (sub)folders [LIST]
;   > Nil if nothing found [BOOLEAN]
; Notes:
;   - None
;
(defun MeGetSubFolders (Fld / CurFld)
 (mapcar
 '(lambda (l)
   (setq CurFld (strcat Fld "\\" l))
   (cons CurFld (apply 'append (MeGetSubFolders CurFld)))
  )
  (cddr (vl-directory-files Fld nil -1))
 )
)


[T.Willey]

Thanks Jurg.  I will have to study this one, and try and understand the logic of it, and see if I can do it.

[CAB]

More cool stuff:
Have you seen this?
http://www.theswamp.org/index.php?topic=3683.msg44786#msg44786
or this
http://www.theswamp.org/index.php?topic=1468.msg18839#msg18839
another good one
http://www.theswamp.org/index.php?topic=820.msg11076#msg11076
and the finalle
http://www.theswamp.org/index.php?topic=4064.msg48504#msg48504

[T.Willey]

Thanks Alan.  I have a lot of reading to do.

I remember reading some when I first tried to figure out recursion, but not when I tried to write this one.  I like to write code blindly (not getting help from any source besides the help files), so that I can learn more, but I think I'm over my head here, and need the help.

[CAB]

Here is some commented code:
http://www.theswamp.org/index.php?topic=3683.msg44477#msg44477

I typically avoid recursion if I can, makes my head hurt too.

[T.Willey]

Thanks again Alan.  I love learning, even more when it's hard to grasp at first.  This will take a lot of time for me.  I love having things to learn, that I want to learn.

[LE]

It may not be what you are trying to do, but might be useful:

Two old functions. . .

Code: [Select]

;;; Usage: (search_sub_folders (getvar "DWGPREFIX") "*.dwg")
;;; Return: (list "subfolder" "files")
;;; (("." "2006generalindex.dwg" "T-1.dwg" "T-2.dwg" "TITLE SHEET.dwg")
;;; (".." "TITLEBLOCK.dwg")
;;; ("HARDSHIP SUBBMITTAL" "2006generalindex.dwg" "T-1.dwg" "T-2.dwg" "TITLE SHEET.dwg")
;;; ("New Folder"))

(defun search_sub_folders (pathfile ext)
  (mapcar '(lambda (sub)
     (cons sub
   (vl-directory-files
     (strcat pathfile sub)
     ext
     1
   )
     )
   )
  (vl-directory-files
    (vl-filename-directory
      pathfile
    )
    nil
    -1
  )
  )
)

;;; (MapSubfolders (search_sub_folders (getvar "DWGPREFIX") "*.dwg"))
;;; ("C:\\My Documents\\" "Piezas.dwg" "ARQCAD_15.dwg" "ARQCAD.dwg")
;;; ("C:\\My Documents\\toiltets\\" "t1000.dwg" "t200.dwg" "t300.dwg")
;;; ("C:\\My Documents\\toiltets\\" "t1000.dwg" "t200.dwg" "t300.dwg")

(defun MapSubfolders (sfolders)
  (setq tmp nil)
  (foreach s sfolders
    (if (= "." (car s))
      (setq
tmp
(append tmp
(list (cons (getvar "DWGPREFIX") (vl-remove "." s)))
)
      )
      (if (/= 1 (length s))
(setq
  tmp (append
tmp
(list (cons (strcat (getvar "DWGPREFIX") (car s) "\\")
    (vl-remove (car s) s)
      )
)
      )
)
      )
    )
  )
)

About recursion... I think I had used twice... if I recall...

[T.Willey]

Thanks Luis.  I will have fun studying these also.

I guess this brings up another questions then.  How many people actually use recursion in codes? and is it useful to know and understand?

Any and all comments welcomed.  If people think this should be a new topic, let me know and I will make a new one in the appropriate location.

[Jeff_M]

Tim, I use recursion when I find it necessary to get an unknown number of objects/sub-objects. You've selected one good example. Another would be Blocks/Xrefs are another since they can be infinitely(nearly) nested.

IMO, search on the Adesk customization newsgroup for discussions that Doug Broad and Michael Puckett were involved with. The 2 of them (and Tony T.) have had some of the best discussions I've seen about the pros & cons of recursion.

[T.Willey]

Thanks Jeff; will do.

[MP]

Hmmm. Briefly, recursion is typically less work work for the programmer (once you wrap your head around it) but conversley more work for the computer, especially the stack that must hold interim results. Also typically, a well written iterative function will run faster than a recursive one, but it will require more coding.

However, some problems lend themselves to recursion better than iterative solutions, like anything that can be nested -- directory structures, blocks, lists etc.

Here's a quick variant that attempts to optimize and illuminate the recursion process a bit by formally declaring local defuns where lambda calls would typically be invoked --

Code: [Select]

(defun GetFolders ( path / _GetFolders _Collector _Main )

    (defun _GetFolders ( path / folders )
        (defun _GetFolders ( path )
            (cddr
                (vl-directory-files path nil -1)
            )
        )
        (if (vl-position "."
                (setq folders
                    (vl-directory-files path nil -1)
                )
            )    
            (cddr folders)
            folders
        )    
    )

    (defun _Collector ( folder / temp )
        (cons
            (setq temp (strcat path "\\" folder))
            (apply 'append (_Main temp))
        )
    )

    (defun _Main ( path )
        (mapcar '_Collector
            (_GetFolders path)
        )
    )

    (apply 'append (_Main path))

)
While it looks verbose it should perform decent enough and is safer than some of the variants already posted (not dissing, just an observation). See the "An aside ..." comment at the end of this post.

If run on a folder structure like this --

Code: [Select]

C:\Folder1
    |
    +-- Folder1
    |   |
    |   +-- Folder1
    |   |
    |   +-- Folder2
    |   |
    |   +-- Folder3
    |
    +-- Folder2
    |   |
    |   +-- Folder1
    |   |
    |   +-- Folder2
    |   |
    |   +-- Folder3
    |
    +-- Folder3
        |
        +-- Folder1
        |
        +-- Folder2
        |
        +-- Folder3
it will return a list of 12 items.

Code: [Select]

(GetFolders "C:\\Folder1")

Code: [Select]

(  "c:\\folder1\\folder1"
    "c:\\folder1\\folder1\\folder1"
    "c:\\folder1\\folder1\\folder2"
    "c:\\folder1\\folder1\\folder3"
    "c:\\folder1\\folder2"
    "c:\\folder1\\folder2\\folder1"
    "c:\\folder1\\folder2\\folder2"
    "c:\\folder1\\folder2\\folder3"
    "c:\\folder1\\folder3"
    "c:\\folder1\\folder3\\folder1"
    "c:\\folder1\\folder3\\folder2"
    "c:\\folder1\\folder3\\folder3"
)
An aside ... using cddr to strip out "." and ".." unconditionally is a little dangerous, as the vl-directory-files function will not include them if you run said function on a root directory like (vl-directory-files "c:\\" nil -1). That's why I redefine the _GetFolders function after the first call. On the first call it checks to see if "." is a member of the result list and if so strips it (and ".." ) out. Thereafter the program uses the redefined version which uses cddr unconditionally, as there is no need to pay the penaly of testing each subsequent iteration.

Hope (that makes sense and) that helps some.

[T.Willey]

Thanks for the example, and explanation.  Hopefully I will get a handle one this style, so that I know when it would be useful to use it.

[MP]

Tim, I use recursion when I find it necessary to get an unknown number of objects/sub-objects. You've selected one good example. Another would be Blocks/Xrefs are another since they can be infinitely(nearly) nested.

IMO, search on the Adesk customization newsgroup for discussions that Doug Broad and Michael Puckett were involved with. The 2 of them (and Tony T.) have had some of the best discussions I've seen about the pros & cons of recursion.

Whoa, I'm honored to be included in the same sentence as those 2. There were times way back when there used to be challenging and fun contests / discussions on the autodesk news servers. Folks like Vladimir Nesterovsky (hope I spelled that correctly) and Reini Urban would sometimes participate in addition to the afore mentioned (sadly this is before google indexed those groups). Those discussion always resulted in me pounded out dozens and dozens of different solution variants, trying to do this, optimize that. Understatement: Very educational. Speaking of Vladimir, it was Vladimir who had recommended a book (Structure And Interpretation of Computer Programs that was instrumental in pushing my lispin' knowledge to the next level. It really changed the landscape for me and "took the reigns and blinders completely off" so to speak (tho I've still lots to learn). I don't know what ever happened to Vladimir, he stopped posting to the ngs long ago (as did Mr. Urban) but I'm sure he excelled at whatever he set his mind to and I'm grateful to this day that he mentioned said book. Thank you Vladimir.

/tangent, but it's your fault for making me think of it.

Anyway, thanks for the props Jeff, appreciate it.

[MP]

My pleasure Tim, thanks for posing the question.