Recursion: Difference between revisions
No edit summary |
m (Added wiki headers and removed unnecessary dotted lines.) |
||
| Line 1: | Line 1: | ||
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. | 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. | 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. | 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: | 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: | ||
<syntaxhighlight lang="autoit"> | <syntaxhighlight lang="autoit"> | ||
_AddOne(0) | _AddOne(0) | ||
| Line 28: | Line 24: | ||
EndFunc | EndFunc | ||
</syntaxhighlight> | </syntaxhighlight> | ||
I get to 3898 and then see: | I get to 3898 and then see: | ||
| Line 36: | Line 31: | ||
But adding a single limit line to prevent the infinite loop will show how recursion can work without this problem: | But adding a single limit line to prevent the infinite loop will show how recursion can work without this problem: | ||
<syntaxhighlight lang="autoit"> | <syntaxhighlight lang="autoit"> | ||
_AddOne(0) | _AddOne(0) | ||
| Line 54: | Line 48: | ||
EndFunc | EndFunc | ||
</syntaxhighlight> | </syntaxhighlight> | ||
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. | 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. | 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: | 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: | ||
<syntaxhighlight lang="autoit"> | <syntaxhighlight lang="autoit"> | ||
ListFiles_Recursive(@ProgramFilesDir & "\AutoIt3\Extras") | ListFiles_Recursive(@ProgramFilesDir & "\AutoIt3\Extras") | ||
| Line 100: | Line 91: | ||
EndFunc ;==>ListFiles_Recursive | EndFunc ;==>ListFiles_Recursive | ||
</syntaxhighlight> | </syntaxhighlight> | ||
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. | 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. | 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: | 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: | ||
<syntaxhighlight lang="autoit"> | <syntaxhighlight lang="autoit"> | ||
ListFiles_Iterative(@ProgramFilesDir & "\AutoIt3\Extras") | ListFiles_Iterative(@ProgramFilesDir & "\AutoIt3\Extras") | ||
| Line 167: | Line 155: | ||
EndFunc ;==>ListFiles_Iterative | EndFunc ;==>ListFiles_Iterative | ||
</syntaxhighlight> | </syntaxhighlight> | ||
As you can see, you get the same files listed - and no recursion used at all! | 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. | 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. | ||
Revision as of 13:13, 11 November 2012
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.