# 384 recursive call limit?

## Recommended Posts

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.

##### Share on other sites

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

http://www.myclanhosting.com/defiasVisit Join and contribute to a soon to be leader in Custumized tools development in [C# .Net 1.1 ~ 2.0/C/C++/MFC/AutoIt3/Masm32]

##### Share on other sites

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

David Nuttall
Nuttall Computer Consulting

An Aquarius born during the Age of Aquarius

AutoIt allows me to re-invent the wheel so much faster.

I'm off to write a wizard, a wonderful wizard of odd...

##### Share on other sites

just wondering why this was chosen instead of like

If WIN9x Then limit = 384

else limit = 512

?

Edited by w0uter

My UDF's:;mem stuff_Mem;ftp stuff_FTP ( OLD );inet stuff_INetGetSource ( OLD )_INetGetImage _INetBrowse ( Collection )_EncodeUrl_NetStat_Google;random stuff_iPixelSearch_DiceRoll

##### Share on other sites

just wondering why this was chosen instead of like

If WIN9x Then limit = 384

else limit = 512

?

Portability, I guess.

##### Share on other sites

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.

##### Share on other sites

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 by Nutster

David Nuttall
Nuttall Computer Consulting

An Aquarius born during the Age of Aquarius

AutoIt allows me to re-invent the wheel so much faster.

I'm off to write a wizard, a wonderful wizard of odd...

##### Share on other sites

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

[quote]Together we might liveDivided we must fall[/quote]

##### Share on other sites

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

##### Share on other sites

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 by VicTT

[quote]Together we might liveDivided we must fall[/quote]

##### Share on other sites

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.

##### Share on other sites

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.

David Nuttall
Nuttall Computer Consulting

An Aquarius born during the Age of Aquarius

AutoIt allows me to re-invent the wheel so much faster.

I'm off to write a wizard, a wonderful wizard of odd...

##### Share on other sites

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 by LxP

##### Share on other sites

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 by Valik

##### Share on other sites

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 by LxP

##### Share on other sites

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.

```#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
\$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
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.

##### Share on other sites

@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)?

Who else would I be?

##### Share on other sites

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

##### Share on other sites

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.

Who else would I be?

## Create an account

Register a new account