Difference between revisions of "Recursion"
From ROBOTC API Guide
(→Recursion) |
|||
(2 intermediate revisions by one user not shown) | |||
Line 9: | Line 9: | ||
|- | |- | ||
| Recursion is the ability for a function to call itself. Normally for a function to be called it must be created and then called from task main. However, with recursion a function can call itself multiple times; the downside of this is that until a function reaches its end brace '}' or reaches a 'return' command, it will stay in memory. This can lead to situations where the available memory fills up with too many concurrently running functions and causes a crash. Recursion in ROBOTC works on a "Last In First Out" (LIFO) process; the most recent function called will be the first one closed when a return command or an end brace '}' is reached. | | Recursion is the ability for a function to call itself. Normally for a function to be called it must be created and then called from task main. However, with recursion a function can call itself multiple times; the downside of this is that until a function reaches its end brace '}' or reaches a 'return' command, it will stay in memory. This can lead to situations where the available memory fills up with too many concurrently running functions and causes a crash. Recursion in ROBOTC works on a "Last In First Out" (LIFO) process; the most recent function called will be the first one closed when a return command or an end brace '}' is reached. | ||
+ | <br /> | ||
|- | |- | ||
|For example, see the program below. First, a function called 'looping' is created and initialized. Inside of it there is a single 'return' command, which exits the function and 'returns' the program flow back to where the function was originally called from. Next, there is task main with a single call to the function 'looping'. | |For example, see the program below. First, a function called 'looping' is created and initialized. Inside of it there is a single 'return' command, which exits the function and 'returns' the program flow back to where the function was originally called from. Next, there is task main with a single call to the function 'looping'. | ||
|- | |- | ||
− | |[[File: | + | |[[File:Recursion_Return.png]] |
+ | <br /> | ||
|- | |- | ||
|When the program runs, the function 'looping' is created and the program starts at task main. The first command in task main is to call the function 'looping'. The Call Stack debugger window shows both task main and the function 'looping' being in memory at this point. | |When the program runs, the function 'looping' is created and the program starts at task main. The first command in task main is to call the function 'looping'. The Call Stack debugger window shows both task main and the function 'looping' being in memory at this point. | ||
|- | |- | ||
|[[File:Recursion_Return_Two.png]] | |[[File:Recursion_Return_Two.png]] | ||
+ | <br /> | ||
|- | |- | ||
|After 'looping' is called, its first command is to return to task main. This ends the function and clears it from memory (since the function has been exited, this can be seen in the Call Stack debugger window). | |After 'looping' is called, its first command is to return to task main. This ends the function and clears it from memory (since the function has been exited, this can be seen in the Call Stack debugger window). | ||
|} | |} | ||
− | + | <br /> | |
== Memory Overload == | == Memory Overload == | ||
{| | {| | ||
|One of the major issues that can arise when utilizing recursion is memory overload. This occurs when the onboard memory of a computer system or microprocessor is filled beyond maximum, or 'overloaded'. | |One of the major issues that can arise when utilizing recursion is memory overload. This occurs when the onboard memory of a computer system or microprocessor is filled beyond maximum, or 'overloaded'. | ||
|- | |- | ||
− | |In the next example, we have simply placed a recursive call in 'looping' back to itself before the 'return' command. Now, each time 'looping' is called it reaches the recursive command first and opens up another copy of the function in memory. Since the program flow is directed to the new calling of the function before the return command or a | + | |In the next example, we have simply placed a recursive call in 'looping' back to itself before the 'return' command. Now, each time 'looping' is called it reaches the recursive command first and opens up another copy of the function in memory. Since the program flow is directed to the new calling of the function before the return command or a closing brace is reached, each function remains open in memory. |
|- | |- | ||
|[[File:Recursion_Overload.png]] | |[[File:Recursion_Overload.png]] | ||
+ | <br /> | ||
|- | |- | ||
|This eventually overloads the memory and causes a crash. | |This eventually overloads the memory and causes a crash. | ||
|- | |- | ||
|[[File:Recursion_Error.png]] | |[[File:Recursion_Error.png]] | ||
+ | <br /> | ||
|- | |- | ||
|} | |} | ||
Line 45: | Line 50: | ||
|- | |- | ||
|[[File:Recursion_If_Else.png]] | |[[File:Recursion_If_Else.png]] | ||
+ | <br /> | ||
|- | |- | ||
|A variant of this program that also works is to utilize parameters. By creating 'looping' with the integer x as its parameter, we can pass a value of 0 from task main and increment the value of x when it is passed to a new copy of looping every time recursion occurs. | |A variant of this program that also works is to utilize parameters. By creating 'looping' with the integer x as its parameter, we can pass a value of 0 from task main and increment the value of x when it is passed to a new copy of looping every time recursion occurs. | ||
|- | |- | ||
|[[File:Recursion_If_Params.png]] | |[[File:Recursion_If_Params.png]] | ||
+ | <br /> | ||
|- | |- | ||
|} | |} |
Revision as of 03:12, 4 September 2012
General Programming → Recursion
|
Recursion
Memory Overload
Controlled Recursion
Ending Functions
If the above programs are manually stepped through, there will be 5 steps to go through before task main is returned to. Remember, each time a function is called it opens another 'copy' of the function. Those extra steps are for the first, second, third, and fourth copies of the 'looping' function. The functions only clear out of memory when their end brace '}' or a return command is reached. |