Recursion

Recursion is a topic which many find difficult to grasp and even more difficult to realise. However, as I hope this tutorial will show, it is not that daunting and can prove very useful. However, you do need to take great care when using recursion, including tidying up after yourself, as otherwise you can crash your system very quickly.

What is recursion?

Let us start by explaining what is meant by recursion. Basically it means a function calling itself while the original function is still running. You might wonder why you would ever want to do this - perhaps the simplest example is searching through a folder structure where you need to look in each of the subfolders you find at each level. Another example would be my GUIFrames UDF where I use recursion to resize the frames inside a resized GUI, even if the frames are inside other frames - each resized element uses the same function to resize the elements within it. Without recursion this would be almost impossible to do.

Why is recursion difficult to use?

So now we know what recursion is, why is it tricky to use? The following is a very simplistic explanation, but it will suffice to illustrate the problem. Like any other application, AutoIt maintains an area of memory known as the stack where it stores temporary data. When you call a function, AutoIt puts a fair amout of data onto the stack so that it can reload it when the function returns and so knows where it was, what it was doing and what the various variable values were. If you call other functions from within the running function, the amount of data in the stack increases each time and if you do it enough times you can get a "stack overflow" error which usually spells disaster! Of course, most scripts do not nest functions to any great depth and the stack is comfortably large enough to cope as the data is removed once the function returns. But recursion, where a function keeps calling itself, can lead to a very rapid increase in the amount of stack space required and so a rapid crash. AutoIt actually prevents the crash by limiting the recursion level - it will not allow you to store too many datasets (i.e. call too many functions without ever getting back to the main idle loop) on the stack. It is extremely unlikely that you would ever get anywhere close to this limit unless you get into a recursive loop with a function calling itself.

Some simple examples - bad and good!

So what does a recursive loop look like? Here is a very simple example which on first glance looks as if it will just print an ever-increasing value in the console. But try running it - it will not work as you might think, but it will not harm your machine:

 _AddOne(0)
 
 Func _AddOne($i)
 
     ConsoleWrite("In: " & $i & @CRLF)
 
     $i += 1
 
     _AddOne($i)
 
     ConsoleWrite("Out: " & $i & @CRLF)
 
 EndFunc

I get to 3898 and then see:

M:\Program\Au3 Scripts\Recursion Demo.au3 (13) : ==> Recursion level has been exceeded - AutoIt will quit to prevent stack overflow.:

As you see, you get the "In" values printed, but as you immediately call the function again you never get to see the "Out" values as you never actually reach that point in the function - you are in an infinite recursive loop and only AutoIt's built-in limit prevents a crash as the stack approaches overflow.

But adding a single limit line to prevent the infinite loop will show how recursion can work without this problem:

 _AddOne(0)
 
 Func _AddOne($i)
 
     ConsoleWrite("In: " & $i & @CRLF)
 
     $i += 1
 
     If $i = 100 Then Return ; This is where we break the infinite recursive loop <<<<<<<<<<<<<<<<<<<<<<<<<<
 
     _AddOne($i)
 
     ConsoleWrite("Out: " & $i & @CRLF)
 
 EndFunc

Here you can see that the "In" values are printed as before until the limit is reached and the final function returns. This triggers all the other functions that had been called to continue to run and you get the "Out" values printed. Note that they are in the reverse order as AutoIt pulls the data back from the stack and resets each function to the state it was in before the recursive call.

A practical use of recursion

I hope the above has made it clear what recursion is and why you must make sure that you do not enter an infinite recursive loop. Let us now look at a practical application of recursion - searching a folder tree.

The problem is simple - we need to search an initial folder - and any subfolders that we find within that folder - and any subfolders within those subfolders - and any subfolder within those subfolders...... You can see why recursion might be useful here! This is a very simple script to list the files in the "Extras" folder of your AutoIt install:

 ListFiles_Recursive(@ProgramFilesDir & "\AutoIt3\Extras")
 
 Func ListFiles_Recursive($sSourceFolder)
 
     Local $sFile
 
     ; Force a trailing \
     If StringRight($sSourceFolder, 1) <> "\" Then $sSourceFolder &= "\"
 
     ; Start the search
     Local $hSearch = FileFindFirstFile($sSourceFolder & "*.*")
     ; If no files found then return
     If $hSearch = -1 Then Return ; This is where we break the recursive loop <<<<<<<<<<<<<<<<<<<<<<<<<<
 
         ; Now run through the contents of the folder
         While 1
             ; Get next match
             $sFile = FileFindNextFile($hSearch)
             ; If no more files then close search handle and return
             If @error Then ExitLoop  ; This is where we break the recursive loop <<<<<<<<<<<<<<<<<<<<<<<<<<
 
             ; Check if a folder
             If @extended Then
                 ; If so then call the function recursively
                 ListFiles_Recursive($sSourceFolder & $sFile)
             Else
                 ; If a file than write path and name
                 ConsoleWrite("Found: " & $sSourceFolder & $sFile & @CRLF)
             EndIf
         WEnd
 
         ; Close search handle
         FileClose($hSearch)
 
 EndFunc   ;==>ListFiles_Recursive

The 2 <<<<<<<<<<< lines are the limiters to prevent infinite recursion. The first returns when the FileFindFirstFile does not find any files in a folder, the second when FileFindNextFile finds no more files in a folder. Take careful note of the difference in the action the 2 limiters take - the first returns instantly, the second exits the loop to make sure that the $hSearch handle is closed before returning. This is a good example of the "tidying up" I mentioned right at the beginning - there are only a limited number of handles available and leaving one open each time you call a recursive function is a good recipe for a catastophe later on.

I hope this short introduction to recursion has clarified what it is and why you need to take such care when using it. However, I would advise you not to use recursion unless there is absolutely no alternative. Unless you take extreme care, it is simply too easy to mess up the limiters and end up in an infinite recursive loop.

A way of avoiding of recursion

So what can you do when recursion seems the obvious and best solution? One possibility is to look at iteration, where you call a function several times but return from it each time and then restart it with another set of parameters. Here is a very similar file listing script to the example above using an iterative technique. Each time a subfolder is found its path is added to an array and the internal loop continues until all them have been searched:

 ListFiles_Iterative(@ProgramFilesDir & "\AutoIt3\Extras")
 
 Func ListFiles_Iterative($sSourceFolder)
 
     Local $sFile
 
     ; Force a trailing \
     If StringRight($sSourceFolder, 1) <> "\" Then $sSourceFolder &= "\"
     ; Create an array to hold the folders to be searched
     Local $aFolderList[10] = [1, $sSourceFolder]
 
     ; Search within listed folders until all have been searched
     While $aFolderList[0] > 0
 	
         ; Get path of folder to search
         Local $sSearchPath = $aFolderList[$aFolderList[0]]
         ; Remove folder from list
         $aFolderList[0] -= 1
 
         ; Start the search
         Local $hSearch = FileFindFirstFile($sSearchPath & "*.*")
         ; If failure then return
         If $hSearch = -1 Then Return
 	
         ; Now run through the contents of the folder
         While 1
             ; Get next match
             $sFile = FileFindNextFile($hSearch)
             ; If no more files then close search handle and return
             If @error Then ExitLoop
             ; If a folder then add to array to be searched
             If @extended Then
 	
                 ; #######################################
 	
                 ; Increase folder count
                 $aFolderList[0] += 1
                 ; Double array size if too small (fewer ReDim needed)
                 If UBound($aFolderList) <= $aFolderList[0] Then ReDim $aFolderList[UBound($aFolderList) * 2]
                 ; Add folder
                 $aFolderList[$aFolderList[0]] = $sSearchPath & $sFile & "\"
 		
                 ; #######################################
 	
             Else
                 ; If a file than write path and name
                 ConsoleWrite("Found: " & $sSearchPath & $sFile & @CRLF)
             EndIf
         WEnd
 
         ; Close search handle
         FileClose($hSearch)
 
     WEnd
 
 EndFunc   ;==>ListFiles_Iterative

As you can see, you get the same files listed - and no recursion used at all!

A little added extra

If you have been good enough to read this far, you might like to look carefully at the code between the ######## lines in the example above where the subfolders found are added to the $aFolderList array. The code uses a clever trick to speed up the script. ReDim is among the slowest of the AutoIt functions, so you want to limit its use as much as possible. If we were to increase the array size by just the one element each time we added a folder, we would slow down the function enormously - it makes little difference here but imagine if you were scanning an entire drive. Instead of adding a single additional element we double the array in size if it is already full to make sure we get plenty of extra space. You will need to have a count variable available to do this - so why not in the [0] element as is the case for many AutoIt arrays? Just remember that if you want to use the array subsequently (unlike here where it is discarded) you will need one final ReDim to get rid of any unused elements left over after the last increase in size.