Using recursion or iteration in AutoIT?

[Mithrandir]

I'm making a function -I think that it's actually a procedure- that has as parameters two arrays. One of them is the stack of the recursion which I named $recursivearray . Since I don't know whether AutoIT has special rules for recursion -and I also didn't understand quite well my lessons at university with Modula-2 - I would like to know:

1) Do I have to pass the arrays by reference (Byref) ? I guess that I have to because I'm modyfing them.

2) I am also a bit confused with the recursive calls and variables passed by reference. From what I understood, in each recursive call a copy of the variables that are passed as parameters is made. If that's the case I would have to make an iterative function because I want to modify both arrays. I would appreciate any help with this

I'm going to post the pseudo-code because the actual code is really long and I don't need any help in anything specific, in any case I can post all the real code:

Func Recursive(Byref $recursivearray,Byref $arrayofresults);

    If UBound($recursivearray) = 0 Then
        Return
    Else
        $elem = _ArrayPop($recursivearray);Note: since using _ArrayPop with an array with 1 element leaves it as "" I have to start the ;recursion with at least 2 elements because it would cause an error when trying to insert into an array that is nulled
        If condition1 Then
                   If UBound($recursivearray) > 1 Then;because when the array size is 1, arrayadd does not insert in index 0 but 1
                      _ArrayAdd($recursivearray)
                   Else 
                       _ArrayInsert($recursivearray,0,$value1)
                   EndIf
                   ;Here I do some things with other variables
        EndIf
                If condition2 Then
                   If UBound($arrayofresults) > 1 Then;because when the array size is 1, arrayadd does not insert in index 0 but 1
                      _ArrayAdd($arrayofresults,$value2)
                   Else 
                       _ArrayInsert($arrayofresults,0,$value2)
                   EndIf
                   ;Here I do some things with other variables
        EndIf
    Recursive($recursivearray)
        EndIf
EndFunc

Thanks for your help!!

Edited December 29, 2010 by Mithrandir

[Mithrandir]

Sorry I almost forget to report about this: I tried the code but for some reason after a while the code interrupted its execution. I say for some reason because even though I debugged it by adding trace lines everywhere using that option in tools no error came up. The script just stopped the execution after some time. I even tried removing the 'Return' in order to make an infinite loop but the recursion stopped after the same time more or less. The only thing that is left is that the Maximum depth of recursive function calls which the FAQ of autoit says it's of 5100 levels had been reached. However I am not too sure and I would appreciate the input of someone that is more experienced in recursion. Concerning the code, I modified it to make it iterative and it worked:

Func Recursive(Byref $recursivearray,Byref $arrayofresults);

    While UBound($recursivearray) <> 0        
    
        $elem = _ArrayPop($recursivearray);Note: since using _ArrayPop with an array with 1 element leaves it as "" I have to start the ;recursion with at least 2 elements because it would cause an error when trying to insert into an array that is nulled
        If condition1 Then
                   If UBound($recursivearray) > 1 Then;because when the array size is 1, arrayadd does not insert in index 0 but 1
                      _ArrayAdd($recursivearray)
                   Else 
                       _ArrayInsert($recursivearray,0,$value1)
                   EndIf
                   ;Here I do some things with other variables
        EndIf
                If condition2 Then
                   If UBound($arrayofresults) > 1 Then;because when the array size is 1, arrayadd does not insert in index 0 but 1
                      _ArrayAdd($arrayofresults,$value2)
                   Else 
                       _ArrayInsert($arrayofresults,0,$value2)
                   EndIf
                   ;Here I do some things with other variables
        EndIf
    WEnd
        
EndFunc

[Melba23]

Mithrandir,

Using recursion or iteration in AutoIT?

Now that is a question!

Personally I try to avoid recursion if at all possible - too much chance of it screwing up not properly unwound after each call. But sometimes it is impossible to avoid and then you need to take the utmost care to make sure you do completely unwind every time. I think the only time I have seriously used recursion in AutoIt is in the GUIFrames UDF to adjust all the affected child frames when a frame is resized - it seems to work!

As to parameter passing, I believe that if you are modifying a variable or array within each call then you must pass it ByRef so that each time the function is called it gets the current version. If you were to pass "by Value" then each call would be working on its own copy - hardly a recipe for success as the modifications made in each call would not be noticed on return!

Just for interest, I have attached a script which includes 2 very stripped down development versions of my RecFileListToArray UDF - it shows the difference between a recursive and an iterative (stack) version which lists the folders on a path. I went with the iterative version for the release although the recursive version worked well. Of interest there was very little speed difference between them when all the other UDF code was added. I hope it might be of interest:

expandcollapse popup

#include <Array.au3>

$aArray = _FLTA_Recur("Your_Path")
_ArrayDisplay($aArray)

$aArray = _FLTA_Stack("Your_Path")
_ArrayDisplay($aArray)

; ---------------------------------------

Func _FLTA_Recur($sPath)

    Local $asFoundList[1] = [0]

    ; Check valid path
    If Not FileExists($sPath) Then Return
    ; Ensure trailing \
    If StringRight($sPath, 1) <> "\" Then $sPath = $sPath & "\"

    ; Search recursively
    _FLTA_Recur_Search($sPath, $asFoundList)

    ; Remove unused array elements from last ReDim
    ReDim $asFoundList[$asFoundList[0] + 1]

    Return $asFoundList

EndFunc   ;==>_FLTA_Rec

Func _FLTA_Recur_Search($sCurrentPath, ByRef $asFoundList)

    Local $hSearch, $sName, $fFolder, $sReturnPath = ""

    ; Search folder
    $hSearch = FileFindFirstFile($sCurrentPath & "*")
    If $hSearch = 0 Then Return ; Folder empty

    While 1

        $sName = FileFindNextFile($hSearch)
        ; Check for end of folder
        If @error Then ExitLoop

        ; If folder, add to found list
        If @extended Then ; @extended set if folder

            ; Increase item count
            $asFoundList[0] += 1
            ; Double array size if too small (fewer ReDim needed)
            If UBound($asFoundList) <= $asFoundList[0] Then ReDim $asFoundList[UBound($asFoundList) * 2]
            ; Add to found array
            $asFoundList[$asFoundList[0]] = $sCurrentPath & $sName

            ; Search folder
            _FLTA_Recur_Search($sCurrentPath & $sName & "\", $asFoundList)

        EndIf

    WEnd

    FileClose($hSearch)

EndFunc   ;==>_FLTA_Recur_Search

; ---------------------------------------

Func _FLTA_Stack($sInitialPath)

    Local $asFoundList[1] = [0], $asFolderList[3] = [1]
    Local $sCurrentPath, $hSearch, $sName, $fFolder

    ; Check valid path
    If Not FileExists($sInitialPath) Then Return SetError(1, 1, "")
    ; Ensure trailing \
    If StringRight($sInitialPath, 1) <> "\" Then $sInitialPath = $sInitialPath & "\"
    ; Add path to folder list
    $asFolderList[1] = $sInitialPath

    ; Search in listed folders
    While $asFolderList[0] > 0

        ; Set path to search
        $sCurrentPath = $asFolderList[$asFolderList[0]]
        ; Reduce folder array count
        $asFolderList[0] -= 1
        ; Get search handle
        $hSearch = FileFindFirstFile($sCurrentPath & "*")
        ; If folder empty move to next in list
        If $hSearch = -1 Then ContinueLoop

        ; Search folder
        While 1

            $sName = FileFindNextFile($hSearch)
            ; Check for end of folder
            If @error Then ExitLoop

            ; If folder, add to folder list and found list
            If @extended Then ; @extended set if folder

                ; Increase folder array count
                $asFolderList[0] += 1
                ; Double folder array size if too small (fewer ReDim needed)
                If UBound($asFolderList) <= $asFolderList[0] + 1 Then ReDim $asFolderList[UBound($asFolderList) * 2]
                ; Add subfolder to list
                $asFolderList[$asFolderList[0]] = $sCurrentPath & $sName & "\"

                ; Increase return array count
                $asFoundList[0] += 1
                ; Double return array size if too small (fewer ReDim needed)
                If UBound($asFoundList) <= $asFoundList[0] Then ReDim $asFoundList[UBound($asFoundList) * 2]
                ; Add required path to file/folder name and add to array
                $asFoundList[$asFoundList[0]] = $sCurrentPath & $sName

            EndIf

        WEnd

        ; Close current search
        FileClose($hSearch)

    WEnd

    ; Remove unused return array elements from last ReDim
    ReDim $asFoundList[$asFoundList[0] + 1]

    Return $asFoundList

EndFunc   ;==>_FLTA_Stack

By the way, you may wonder why the 2 arrays in the iterative version contain the same elements (the found folders) in a different order - remember the full version can look for files as well as folders, this stripped down version just lists the folders.

M23

[MvGulik]

Just for interest, I have attached a script which includes 2 very stripped down development versions of my RecFileListToArray UDF

Cool, Don't mind experimenting with that a bit ... although later.

(why don't you make a separate/dedicated Example topic for your RecFileListToArray UDF. Think it deserve it. )

Edited January 7, 2011 by MvGulik

[Melba23]

MvGulik,

Because it is one of many such recursive listing scripts and not the fastest by any means. I just link to the latest iteration in my sig.

M23

[Klaatu]

Instead of passing the array to itself over and over again with each recursion, perhaps it would work better just to make the array a static variable instead.

Just something to think about anyway...