384 recursive call limit?

[LxP]

Hi devs,

I was browsing the 'Current Technical Limits' section of the AutoIt help file and I learnt that a function can be recursively called to 384 levels before AutoIt will complain.

I'm curious as to why 384 is the chosen limit though -- to my untrained eye it would seem easier to work with a power of 2 (like 256 or 512) and not something inbetween.

[WSCPorts]

128 + 256 = 384 still a multiple of 2 but a odd one

[Nutster]

It was chosen because Win95/98 could bomb out before 512 recurrsions.

[w0uter]

just wondering why this was chosen instead of like

If WIN9x Then limit = 384

else limit = 512

?

Edited September 23, 2005 by w0uter

[Josbe]

just wondering why this was chosen instead of like

If WIN9x Then limit = 384

else limit = 512

?

Portability, I guess.

[Richard Robertson]

AutoIt is so portable, it works on a cheese sandwich.

Believe me, its good.

Anyways, thats a good question, why not leave it at 256 though? Makes a bit more sense.

[w0uter]

more recursion = more possibilities

[Nutster]

Anyways, thats a good question, why not leave it at 256 though? Makes a bit more sense.

We want as much versitility as possible. Therefore we (Jon actually) set this limit when 512 recursions bombed out on my Windows 98 box. So we went down to the current level. Besides, if you go deeper than a few dozen levels, it usually means that you have some run-away recurrsion any way. Well, I have some plans to make this limit obsolete, but that is still some ways away (Bug fixes first, then new features). Edited September 25, 2005 by Nutster

[VicTT]

I'm also interested in this topic..AND unlimited recursion..I considered this a major flaw of AutoIt..along with Strings not being able to hold nulls..The string part was fixed..We're awaiting your magic, Nutster..

[Confuzzled]

I'm also interested in this topic..AND unlimited recursion..I considered this a major flaw of AutoIt..along with Strings not being able to hold nulls..The string part was fixed..We're awaiting your magic, Nutster..

Why would you need recursion in structured code?

Compile, run, curse. Recompile, rerun, recurse...

[VicTT]

Because it's a feature of every other big language..you can try Dynamic Programing without recursion but I'll bet you'll spend your whole life trying to cope without it..The same with Backtracking..there are certain cases where doing something recursively is much more feasible..

I'd much rather code

Func Fib($n)
Return _Iif("n>=3",Fib($n-1)+Fib($n-2),1)
EndFunc

than it's iterative counter-part..

Edited September 29, 2005 by VicTT

[ligenza]

Because it's a feature of every other big language..you can try Dynamic Programing without recursion but I'll bet you'll spend your whole life trying to cope without it..The same with Backtracking..there are certain cases where doing something recursively is much more feasible..

I'd much rather code

Func Fib($n)
Return _Iif("n>=3",Fib($n-1)+Fib($n-2),1)
EndFunc

than it's iterative counter-part..

I'd be hard pressed to find any programmer who is anti-recusion. This is a vital feature in my opinion.

[Nutster]

Because it's a feature of every other big language..you can try Dynamic Programing without recursion but I'll bet you'll spend your whole life trying to cope without it..The same with Backtracking..there are certain cases where doing something recursively is much more feasible..

I'd much rather code

Func Fib($n)
   Return _Iif("n>=3",Fib($n-1)+Fib($n-2),1)
EndFunc

than it's iterative counter-part..

Keep in mind though that recurssion can be much slower than a well-designed loop. Compare your function to this one:

Func Fib(const $n)
    if $n = 1 or $n = 2 then
        return 1
    elseif $n < 1 then
        return 0
    else
        Dim $i1 = 1, $i2 = 1, $count, $tmp

        for $count=3 to $n
           $tmp = $i1 + $i2
           $i1 = $i2
           $i2 = $tmp
        next 
        return $i2
    endif
EndFunc

You only need recursion when you need to store dynamic state information about your passes. Take a look at the quick sort algoithum for a good example of that. Each pass needs its own state (start, end) information, so store these on the stack.

[LxP]

I can't really agree that recursion is the best method for generating Fibonacci sequences -- as $n increases, the number of calculations required for an end result compared to that of its iterative counterpart are astronomical.

Recursiveness is definitely needed** for things like directory and registry traversal however.

** My programming lecturer refuses to say that it's impossible to traverse a directory structure iteratively, but I'll maintain my view until proven otherwise.

Edited September 30, 2005 by LxP

[Valik]

I can't really agree that recursion is the best method for generating Fibonacci sequences -- as $n increases, the number of calculations required for an end result compared to that of its iterative counterpart are astronomical.

Recursiveness is definitely needed** for things like directory and registry traversal however.

** My programming lecturer refuses to say that it's impossible to traverse a directory structure iteratively, but I'll maintain my view until proven otherwise.

It's possible to non-recursively iterate across a directory structure:

Code Removed, see below.

Edit: The code is pretty slow. That's a product of how it's written (string-based storage) and not because it doesn't use recursion. I can probably improve it by using arrays instead of strings for storage.

Edited September 30, 2005 by Valik

[LxP]

Wow Valik -- your code fascinates me. I must admit that I was expecting something much more complex -- it didn't really occur to me to use an indefinite Do..Until loop and a stack- or queue-type structure for holding directories.

For what it's worth, my thinking was more along the lines of a definite loop through file names, and then directory names -- and then of course from there...? Mental blank.

The concept of this code will definitely be very valuable to me in the future. Thanks very much for your time spent writing it.

Edit: Missing a few words.

Edited September 30, 2005 by LxP

[Valik]

Wow Valik -- your code fascinates me. I must admit that I was expecting something much more complex -- it didn't really occur to me to use an indefinite Do..Until loop and a stack- or queue-type structure for holding directories.

For what it's worth, my thinking was more along the lines of a definite loop through file names, and then directory names -- and then of course from there...? Mental blank.

The concept of this code will definitely be very valuable to me in the future. Thanks very much for your time spent writing it.

Edit: Missing a few words.

Well, I should thank you, too. I decided to revise the code to use arrays to be a bit faster and in the process I discovered a bug where an empty directory would pre-maturely cause the function to abort even if it still had other directories to traverse. All my test directories had files in them so I didn't notice this bug. Also, thank you for the inspiration to rewrite it. It's a couple hundred percent faster using arrays as opposed to strings:

Test 1: 16633 files.

Time1: 1096156.99034374

Test 2: 16633 files.

Time2: 4404.37290214259

Test 1 used the code I posted above (I fixed the bug in my test and I've since removed the code because it sucks). Test 2 uses the code below* which is very similar in design to the first example but uses arrays instead of strings. I also found a bug where the pattern wasn't working correctly (Stupid logic there). So now I've replaced the pattern/filter with include/exclude parameters. These accept regular expression patterns to include and exclude with exclude getting priority (Things matching both expressions will not be included). The default is to match anything and exclude nothing. This change had a negligible impact on speed.

expandcollapse popup

#Region _FileSearch()
; ===================================================================
; _FileSearch(ByRef $aFileStack, $sRoot, $sInclude = "", $sExclude = "", $bRecurse = True)
;
; Searches the specified directory for files/folders and provides filtering capabilities.
; Parameters:
;   $aFileStack - OUT - Variable used to hold the results.
;   $sRoot - IN - The root directory to start the search in.;   $sRoot - IN -
;   $sInclude - IN/OPTIONAL - Files/folders matching this regular exp[b][/b]ression pattern will be included.
;   $sExclude - IN/OPTIONAL - Files/folders matching this regular exp[b][/b]ression pattern will be excluded.
;       This takes precedence over an include filter.
;   $bRecurse - IN/OPTIONAL - Recurse into sub-directories (Default True).
; Returns:
;   True if one or more files/folders were found, False otherwise.  In the event of failure, an empty
;   the return variable will be an empty string.
; ===================================================================
Func _FileSearch(ByRef $aFileStack, $sRoot, $sInclude = "", $sExclude = "", $bRecurse = True)
    Local $sCurrentDir = $sRoot
    Local $aDirStack[100], $nDirStackSize = 0, $nFileStackSize = 0
    Dim $aFileStack[100]
    Do
        If StringRight($sCurrentDir , 1) <> "\" Then $sCurrentDir &= "\"
        Local $hSearch = FileFindFirstFile($sCurrentDir & "*")
        If $hSearch = -1 And $nDirStackSize = 0 Then ExitLoop
        While True
            Local $sFile = FileFindNextFile($hSearch)
            If @error Then ExitLoop
            If $sFile = "." Or $sFile = ".." Then ContinueLoop
            Local $sCurrentFile = $sCurrentDir & $sFile   ; Convenience
            If $bRecurse Then
                If StringInStr(FileGetAttrib($sCurrentFile), "D") Then
                    If $nDirStackSize = UBound($aDirStack) Then ReDim $aDirStack[Int(UBound($aDirStack) * 1.5)]
                    $aDirStack[$nDirStackSize] = $sCurrentFile
                    $nDirStackSize += 1
                EndIf
            EndIf
            If $sInclude = "" Or (StringRegExp($sCurrentFile, $sInclude)) And ($sExclude = "" Or Not StringRegExp($sCurrentFile, $sExclude)) Then
                If $nFileStackSize = UBound($aFileStack) Then ReDim $aFileStack[Int(UBound($aFileStack) * 1.5)]
                    $aFileStack[$nFileStackSize] = $sCurrentFile
                    $nFileStackSize += 1
            EndIf
        WEnd
        FileClose($hSearch)
       ; Check the directory stack for any elements
        If $nDirStackSize Then
            $nDirStackSize -= 1
            $sCurrentDir = $aDirStack[$nDirStackSize]
        Else
            ExitLoop
        EndIf
    Until False
    If $nFileStackSize = 0 Then
        $aFileStack = ""
        Return False
    Else
        ReDim $aFileStack[$nFileStackSize]
        Return True
    EndIf
EndFunc   ; _FileSearch()
#EndRegion _FileSearch()

* The code used in the test had a bug in the pattern handling. The code above is slightly different than the code in the test. The code above produces results within a very narrow window of what the original (bugged) code did and provides more functionality without the bug.

[this-is-me]

@Valik, Would you mind running a side-by-side comparison between the iterative code and the recursive (* if the recursive will recurse far enough into your test group without crashing autoit)?

[Valik]

@Valik, Would you mind running a side-by-side comparison between the iterative code and the recursive (* if the recursive will recurse far enough into your test group without crashing autoit)?

I wrote a crappy recursive function and discovered that I can't write recursive code or if I did write this half-way decent, recursing sucks. I didn't intentionally try to cripple the recursive version but it's much slower. It was actually harder for me to think of how to do this than write the array version. Anyway, here are my results compared to the function posted above:

Non-Recursive Count: 16633

Non-Recursive Time:4572.37246633301

Recursive Count: 16633

Recursive Time:14348.2213521551

Here is the (crappy) code. The last parameter is for the function-only and shouldn't be called by users:

Func _FileSearchR(ByRef $aFileStack, $sRoot, $sInclude = "", $sExclude = "", $bRecurse = True, $nFileStackSize = 0)
    If Not IsArray($aFileStack) Then Dim $aFileStack[100]
    If StringRight($sRoot , 1) <> "\" Then $sRoot &= "\"
    Local $hSearch = FileFindFirstFile($sRoot & "*")
    If $hSearch <> -1 Then
        While True
            Local $sFile = FileFindNextFile($hSearch)
            If @error Then ExitLoop
            If $sFile = "." Or $sFile = ".." Then ContinueLoop
            Local $sCurrentFile = $sRoot & $sFile   ; Convenience
            If $bRecurse Then
                If $sInclude = "" Or (StringRegExp($sCurrentFile, $sInclude)) And ($sExclude = "" Or Not StringRegExp($sCurrentFile, $sExclude)) Then
                    If $nFileStackSize = UBound($aFileStack) Then ReDim $aFileStack[Int(UBound($aFileStack) * 1.5)]
                    $aFileStack[$nFileStackSize] = $sCurrentFile
                    $nFileStackSize += 1
                EndIf
                If StringInStr(FileGetAttrib($sCurrentFile), "D") Then
                    $nFileStackSize = _FileSearchR($aFileStack, $sCurrentFile, $sInclude, $sExclude, $bRecurse, $nFileStackSize)
                EndIf
            EndIf
        WEnd
        FileClose($hSearch)
    EndIf
    If $nFileStackSize = 0 Then
        $aFileStack = ""
        Return 0
    Else
        ReDim $aFileStack[$nFileStackSize]
        Return $nFileStackSize
    EndIf
EndFunc   ; _FileSearchR()

Note: This code is meant to mimic my other _FileSearch function above. This could, of course, be done differently but then the function would behave differently and that would make the test unfair. Some of the goals with the design in regards to the returned array were that it was a standard array (None of that index 0 = size crap) and that the array was sized to fit. As such, a counter needed to be used to achieve this. Because of the design, non-recursive absolutely kills the recursive version. I'm sure there are other designs where the opposite would hold true. However, I can't find much fault in a fast, non-recursive (no crashing) file search function supporting regular expression searching and filtering. In other words, the function a couple posts back suits my needs fine.

[this-is-me]

Thanks a lot for the comparison. This has certainly been an education to me about converting functions that I once only believed were possible through recursion to iterative functions instead.