Using Recursion
Recursion is the act of a function calling itself. The concept is very theoretical, so it's best understood by working with concrete examples. Say you want to create an application that determines the next highest prime number after a submitted value. The process would work like this:
1. | Increase the submitted number by 1 (because you want to find the next highest number). |
2. | Check if this new number is prime (by checking the remainder when dividing that number by every prime that comes before it). |
3. | If the number is not prime, go back to Step 1. |
4. | If the number is prime, return it. |
As a recursive function, this process could be written like so:
int find_prime(int num) {
short int is_prime = 0; // Flag
++num;
// Calculations to see if num is
prime.
if (is_prime) {
return num;
} else {
find_prime(num);
}
}
This structure creates a loop, continuing to call itself until the is_prime variable is true. With each new call to the find_prime() function, the next highest number is tested.
As when using any loop, one of the most important considerations is that you establish context for recursion to stop. If you don't, you'll have an infinite loop on your hands.
Recursive functions that call themselves as the final act use what is referred to as tail or end recursion. These are the easiest to comprehend because the function's entire code will be executed before the function is called again. If, however, recursion occurs in the middle of a function, this has a unique impact because subsequent statements will be executed in reverse order. Our next example, predicated upon a simple countdown, will better demonstrate this concept.
To use recursion
1. | Create a new file or project in your text editor or IDE. |
2. | Type the standard beginning lines of code (Script 7.5): /* counter.c - Script 7.5 */ #include <stdio.h> Script 7.5. Using recursion, this function counts down from a starting number to an ending one. The second printf() statement helps demonstrate that where recursion occurs in a function affects the end result.
|
3. | Add the function prototype: void countdown (int start, int end); This function takes two integers: a starting number and an ending one. It does not return any values. |
4. | Begin the main function: int main (void) {
|
5. | Call the countdown() function: countdown (50, 40); For recursion to occur at all, the function must be called once. Here the function is called while being passed a starting value of 50 and an ending value of 40. |
6. | Complete the main function: getchar();
return 0;
}
|
7. | After the main function, begin defining the countdown() function: void countdown (int start, int end) {
|
8. | Print the initial value of the start variable: printf ("Before: %d
", start);
To best demonstrate how where recursion occurs in a function—at the beginning, middle, or end—affects its results, this function will print the start value both before and after the recursive call. |
9. | Decrease the value of start: --start; Since this function is counting down, it needs to use the decremental operator. If you wanted to count up, switch this to the incremental operator. |
10. | If the end point has not yet been reached, call this function again: if (start > end) {
countdown (start, end);
}
As long as the start variable is greater than the end variable, this function will continue to call itself. Each time the function is called, start will be worth 1 less but end always stays the same. This conditional is a crucial part of the function definition because it gives the looping structure a stopping point (namely, when start becomes equal to end). |
11. | Reprint the value of start and complete the function: printf ("After: %d
", start);
This print statement reprints the value of start. As you'll see in the end result, this line will not be executed until after start is equal to end, because recursion always occurs up until that point. So if the function were to count down from 3 to 0 (Figure 7.9), Before: 3 is printed, then the function is called again. Before: 2 is printed, the function is called again, and then Before: 1 is printed. start is now equal to 0 (because it's decremented after being printed), so the function is not called again. Figure 7.9. The Before statements occur immediately each time the function is called. The After statements are only executed after recursion is stopped (when start is no longer greater than end).
Now that recursion is over, After: 0 is printed, which completes the innermost function call. The function returns up one level and After: 1 is called. The function returns back to the initial call and After: 2 is printed. |
12. | Save the file as counter.c, compile, and debug as necessary. |
13. | Run the application (Figure 7.10). Figure 7.10. Running the application using the original values (countingdown from 50 to 40).
|
Why Use Recursion?There's an argument to be made that understanding and effectively using recursion may be outside the scope of a beginner's programming book. Conceptually, the idea can be difficult to grasp, but there is merit to being familiar with the technique. Part of the art of programming is the ability to recognize what kind of problem you're facing, and then being able to pick the best tool to solve that problem. Recursion is just one utility you have at your disposal. Although the counter example in this section could be rewritten as a loop, some kinds of problems are best solved with recursive functions. Typically, the problems involve hierarchies, like the hierarchy present in a file system, where directories can contain subdirectories. To browse through the entire structure, you would need to create a function that browses a single directory. If in that directory the function encounters another directory, the function would need to call itself to browse through that subdirectory. Experience will help you understand when loops are adequate and when recursion is the answer. So, even if this example doesn't bring the concept home for you, remember in the back of your mind that recursive functions are available when the time comes. |