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.

[Jürg Menzi]

(...) 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). (...) Hope (that makes sense and) that helps some.

That makes really sense... thanks Michael! I've overlooked that... :ugly:
Must be:

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:
;   - Deep folder structures slow down the function.
;
(defun MeGetSubFolders (Fld / CurFld TmpLst)
 (mapcar
 '(lambda (l)
   (setq CurFld (strcat Fld "\\" l))
   (cons CurFld (apply 'append (MeGetSubFolders CurFld)))
  )
  (if (vl-position "." (setq TmpLst (vl-directory-files Fld nil -1)))
   (cddr TmpLst)
   TmpLst
  )
 )
)


[MP]

No prob Jürg, it's an easy one to miss. I do the redef thing because it would only be a factor on the very first call, even tho the function may be called hundreds or more times thereafter. Tho the performance hit appears nominal when testing for it on every call, I'm so retentive I just couldn't leave it that way.



Now back to nursing my headache.

[Jürg Menzi]

(...) I do the redef thing because it would only be a factor on the very first call, even tho the function may be called hundreds or more times thereafter. Tho the performance hit appears nominal when testing for it on every call, I'm so retentive I just couldn't leave it that way.

Fully agree, but I've chosen the 'second best' way because the time the HW need to scan drive/network is remarkable bigger
than the tiny amount of time for the repetitive call of this comparison - just a guess...

Now back to nursing my headache.

Hope you feel better soon... I know headache only just at the morning after to much single malt... :doa:

[MP]

Hope you feel better soon... I know headache only just at the morning after to much single malt... :doa:

Thanks Jürg. I had a bowl of ibuprofen so it should be gone in a bit.

[JohnK]

<snip>
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.
<snip>

I spoke to him a little bit ago and he said hes still doing a little AutoLisp and C++ but mostly hes into Prolog and Haskel now. He said hes still doing some Scheme too.

Oh yes I agree, that man is amazing. I study his code for days trying to catch all the little neuonces about it. I think im still working on his (Or was it Reni's) Backquoting. I pick it up every once and a while, only to put it down with a hurting head. *smile*

Recursion is a beast. Just when you think you "have it" you learn something new. Just when you think you understand how stack-calls &or info works you get smoked with a weird result in some seeming simple app that throws you back to the begining.

Lately, all the recursion I use is as a simple loop if you will. For instance: (This is the first one I came accross when I searched upwards in my junk file ...its been awhile since ive played arround *huh*)

Code: [Select]

(defun my-getpoint ( pt str / a getpt )
  ;; a general getpoint function for a test I am running.
  ;; Se7en
  ;; 02.24.06
  ;;
  ;; Just a getpoint function that uses grread so that I can tell
  ;; if the user right clicks.
  ;; I am going to STOP the right click for now, I want to add the
  ;; ability to do somethign when the user right clicks later.
  (if (eq pt 'nil)
    (set 'getpt (getpoint str))
    (set 'getpt (getpoint pt str)))
  (setq a (grread getpt 2))
  (if (and a (not (= (car a) 12)))
    (cadr a)
    (my-getpoint pt str)) )
But what all that garbage is doing is something simple like this: If a condition isnt met, do it again. That simple.(This is obviously a bit diff int functionality, but the recurstion is the same.)

Code: [Select]

(defun my-getpoint ( / a )
  (setq a (getpoint "\nPlease pick a point: "))
  (if a
    a
    (my-getpoint)
    )
  )
As MP said, this makes it easier on me to write. (Less code)

SICP is an awesome book. I refer to it constantly. Im always studing that book. I would bet I refer to it at least twice a week. (Well I guess its been about a month since ive actualy played arround with code but when im goofing arround with code I do.)

[CAB]

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.

Thanks for the tip, ordered the book last night. Found a used Hardback in V. good condition for only $40.00.

[ElpanovEvgeniy]

Some time back, I have started to write lessons about recursive functions...
"Lessons of the creation of the recursive functions"
Look, it will be possible interestingly.

The original (RU):
http://www.autocad.ru/cgi-bin/f1/board.cgi?t=25113OT

Machine translation (EN):
http://babelfish.altavista.com/babelfish/trurl_pagecontent?lp=ru_en&trurl=http%3a%2f%2fwww.autocad.ru%2fcgi-bin%2ff1%2fboard.cgi%3ft%3d25113OT

I wish to add, it only the beginning, continuation will be later

[CAB]

Thanks, I tried the English link but got an error.
Sent a message to babelfish about the error.
I hope they can fix it.

[ElpanovEvgeniy]

Thanks, I tried the English link but got an error.
Sent a message to babelfish about the error.
I hope they can fix it.

If you wish, I can make machine translation, but his quality is doubtful...

[MP]

<snip>I spoke to him [Vladimir] a little bit ago and he said hes still doing a little AutoLisp and C++ but mostly hes into Prolog and Haskel now. He said hes still doing some Scheme too.</snip>

Thanks for the update John. I'm not surprised Vladimir plays with Haskell -- a lot of my profs at university were very smitten with it, and said lisp programmers in particular tend to fall real hard for it. I recall hearing "you'd love it" more than once. Anyways, I wish him well.

[JohnK]

I will help Elpanov, clean up his translated article.

[T.Willey]

Some time back, I have started to write lessons about recursive functions...
"Lessons of the creation of the recursive functions"
Look, it will be possible interestingly.

The original (RU):
http://www.autocad.ru/cgi-bin/f1/board.cgi?t=25113OT

Machine translation (EN):
http://babelfish.altavista.com/babelfish/trurl_pagecontent?lp=ru_en&trurl=http%3a%2f%2fwww.autocad.ru%2fcgi-bin%2ff1%2fboard.cgi%3ft%3d25113OT

I wish to add, it only the beginning, continuation will be later

Thanks.  I was able to view the page, but the code doesn't come out right.  I will look, and study it more when I have the time.