Recursion

General Programming → Recursion

Color Key Function: Variable:

Recursion

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.

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

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.

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

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

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.

This eventually overloads the memory and causes a crash.

Controlled Recursion

To use function recursion without running into a memory overload issue, the function must be set up to exit at some point. This can be done a variety of ways.

One such possibility is to set up a simple if-else statement that checks a condition and 'returns' if one of the conditions are met. In the example below, the if-else statement checks to see if the integer variable x (which starts with a value of 0) is less than 5. If it is, x is incremented by one and the function calls itself again. This process repeats until x is no longer less than 5 (the else statement), at which point the function ends and program flow returns to where the function was originally called from.

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.

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.