Using Recursion for Program Repetition
Cool Tricks with Functions
The final part of program repetition is the process of recursion. Recursion is a fairly simple process that allows iteration without using loops. In this topic, you will have a chance to learn about this interesting process. The goal is to give you an introduction to recursion that you will continue using and learn more about later in your Computer Science learning.
Recursive Solutions
Using loops in programming increases the computer's ability to solve problems by repeating certain processes. However, loops are not the only way to repeat a process. Another form of program repetition is called recursion. Recursion quite literally involves having a function call itself with smaller or differing conditions, so that the repetition is implemented through a series of function calls instead of looping. Consider the following program. The user is requested to input a sentence ending with a period. Then the function reverseSentence() is called. This seems like a very simple program.
// display prompt
// function: printString
printString( "Enter a sentence that ends with a period: " );
reverseSentence();
// end line after reversed sentence
// function: printEndline
printEndline();
Now, consider the function that is called.
public static void reverseSentence()
{
// initialize function/variables
char oneChar;
// accept one character from the input stream
// function: getChar
oneChar = getChar();
// check to see that the letter is not a period
if( oneChar != PERIOD )
{
// call the function again
// function: reverseSentence
reverseSentence();
}
// after the function has been called, output the character
// function: printChar
printChar( oneChar );
}
The function reverseSentence() defines a character variable called oneChar, and then inputs one character from the stream (i.e., where the sentence has been typed in), and stores it in the variable oneChar. Then, if the character is not a period, it calls the function reverseSentence() again. A function that calls itself is said to be acting or processing recursively.
Now think about what that call will do. It will define a character variable called oneChar, get another character from the input stream and store it in the variable oneChar, and then if the character is not a period, it will call itself again. To make this process as clear as possible, consider the following computer input process.
Enter a sentence that ends with a period: abc.
The input was "abc.". Now evaluate the process that occurs.
reverseSentence (level 1) is called.
- it captures the character 'a' and stores it in its oneChar variable
- it tests oneChar to see if it holds a period
- oneChar does not hold a period, so . . .
reverseSentence (level 2) is called.
- it captures the character 'b' and stores it in its oneChar variable
- it tests oneChar to see if it holds a period
- oneChar does not hold a period, so . . .
reverseSentence (level 3) is called.
- it captures the character 'c' and stores it in its oneChar variable
- it tests oneChar to see if it holds a period
- oneChar does not hold a period, so . . .
reverseSentence (level 4) is called.
- it captures the character '.' and stores it in its oneChar variable
- it tests oneChar to see if it holds a period
- oneChar does hold a period, so . . .
- reverseSentence (level 4) outputs its character (a period)
- reverseSentence (level 4) finishes its operation,
and returns to its calling function - reverseSentence (level 3)
- reverseSentence (level 3) outputs its character (the character 'c')
- reverseSentence (level 3) finishes its operation,
and returns to its calling function - reverseSentence (level 2)
- reverseSentence (level 2 ) outputs its character (the character 'b')
- reverseSentence (level 2) finishes its operation,
and returns to its calling function - reverseSentence (level 1)
- reverseSentence (level 1) outputs its character (the character 'a')
- reverseSentence (level 1) finishes its operation,
and returns to its calling function - the one that called this function
There are a couple of important notes to identify. First, each time a new reverseSentence() is called, a brand new function is run by the program. This means that in every case, a brand new oneChar variable is defined and used. So with each function running, each oneChar variable holds its own letter or character. This function is fairly trivial.
However, it has accomplished two things you have not been able to do at this point in the course. First, the program is storing a whole list of values, and second it is outputting the list in a different order than it took them in. Later in the course, you will be able to do that with things that hold groups of values called arrays. However, recursion is helping you to accomplish this right now without using the advanced tools.
The recursion works from a simple set of rules.
- there is some base case, or original case where the function completes a simple action
- there is a more generalized case where the function calls itself again with a different parameter
In the case of reverseSentence(), the base case is to capture a character from the front of a list of letters, and output the character. The generalized case is the same as the base case, except the generalized case looks like a smaller version of the base case. The base case in this condition was to take a letter from the front of a list of three letters. The second call to reverseSentence() takes a character from the front of a list of two letters; the third call takes a character from the front of the list of one letter; and the fourth call runs into the limiting condition - there are no more letters to take from the front of the list.
The value of recursion
The letter reversing program shown above demonstrates that you can implement actions such as repetition and data storage using recursive processes. However, the real value of recursion is the simplicity of its approach. If you can find some action that continues to work on smaller parts of itself with the same process, you can gain the value of recursion.
The code is always simpler, and the process is almost always very clear to the reader. Even if a recursive process does not appear obvious, it is not too difficult to track, as shown in the next example.
Consider another problem of calculating factorials. The factorial of a number is that number multiplied by all of the numbers lower than itself. For example, three factorial, shown as 3! is 3 x 2 x 1. Four factorial (i.e., 4!) is 4 x 3 x 2 x 1.
If you think recursively on this, you will see that 4! is actually 4 x 3!, and 3! is actually 3 x 2!, and so on. The pseudo code recursive process for this would look like the following.
// Multiply the given number by the factorial
// of the number one less than the given number
Unfortunately, this would not take care of every condition. If you keep multiplying by the factorial of numbers one less than the one you are holding, sooner or later you are going to run out of numbers. As it turns out, the result of one or zero factorial is one. So the limiting condition for factorials is when the factorial gets down to one or zero. The pseudo code would now be as shown below.
// if the given number is one or less, return 1
// if the number is more than one,
// multiply the given number by the factorial
// of the number one less than the given number
Now then, the code would be just as simple. Note this uses the long data type, which handles longer than normal integers.
long calcFactorial( long number )
{
// check to see if number is less than or equal to one
if( number <= 1 )
{
// return one
return 1;
}
// otherwise, assume number is greater than one
else
{
// return the number multiplied by next factorial below it
// function: calcFactorial
return number * calcFactorial( number - 1 );
}
}
Consider the following graphic.
The above graphical presentation is actually a very effective way for you to analyze the results of a recursive process on paper. It goes without saying that analyzing recursive functions could get confusing. However, using the above format, you can draw out on your paper exactly how a recursive process will work, and calculate the results of a given recursive operation. You can see this strategy applied by watching this video, and then you can make up and work on your own problems. Since the actual action that is taken by the function happens at the end of the function's operation, this function is said to be tail recursive, or simply that it takes its action and finishes the function.
Once you have worked out how to evaluate a recursive function with data, watch this video to see recursive functions in action, and then you can write your own and test them.
Tail recursive functions are good examples of how recursion works, but they can always be replaced by a looping condition. For example, the recursive factorial() function could be replaced by the following loop. Again in this code as well as the code in the recursive functions, the long (i.e., long integer) data type is used to handle larger integer numbers.
// in function where loop is (local)
int number, counter = 1;
long result = 1;
// prompt user for number and acquire
// function: promptForInt
number = promptForInt( "Enter number: " );
// loop from counter up to and including number
while( counter <= number )
{
// multiply running result by next number
result *= counter;
// increment the number
counter++;
}
So, if recursive conditions can be replaced by loops, you might ask what the value of recursion is. The answer is, not all recursive conditions are tail recursive. Take for example a flood fill function that needs to fill a box or some object with characters or colors. The flood fill's base case would be as follows.
if point is inside a box, and no character has been placed there
place a character
The generalized case would be as follows.
if point is inside the box, and no character has been placed there
place a character
then repeat the process in a location one above
then repeat the process in a location one below
then repeat the process in a location one to the right
then repeat the process in a location one to the left
The process to fill every pixel or block inside an irregular shape is very difficult; however, thanks to recursion, the actual code to solve this problem is very simple, as shown here.
void floodFill( int xPos, yPos, char charToPlace, shapeObject shape )
{
// check for character already at location
if( checkInsideShape( xPos, yPos, shape ) )
{
// place a character at the location
placeChar( xPos, yPos, charToPlace, shape );
// call the function to try this above the location
floodFill( xPos, yPos - 1, charToPlace, shape );
// call the function to try this below the location
floodFill( xPos, yPos + 1, charToPlace, shape );
// call the function to try this to the right of the location
floodFill( xPos + 1, yPos, charToPlace, shape );
// call the function to try this to the left of the location
floodFill( xPos - 1, yPos, charToPlace, shape );
}
}
Note that the complicating part of this is the object shape which – being an object-oriented quantity – is beyond the scope of this part of the reference. However, you can still see how simple the recursion makes the flood fill process, and in a pretty small amount of code, it fills every single character or pixel.
The danger of recursion
Actually, recursion is little more hazardous as a programming process than any other loop operations. You must consider what it takes to start the loop or recursion, and you must consider what it takes to stop the loop or recursion. You must also consider the loop control variable or action, which in recursion may not be as obvious as a loop counter or an input operation.
The real loop control action in recursion is the decision for the function to call itself another time. This may be an if statement and/or it may involve the limiting condition, or most likely both. If the decision is valid to call recursion once, and the limiting condition is valid, recursion is both safe and effective.
As would be expected, recursion can get out of control just as a loop can. However, when a loop can repeat "infinitely" (i.e., as long as you let it go on), recursion is self limiting - one way or the other. You should know that there is a certain amount of computer overhead that is consumed anytime any function is called.
If a function calls itself recursively one hundred or one thousand times, most computers will handle this. However, if the function has lost control and is attempting to call itself for the millionth or ten millionth time, the computer is going to run out of stack memory to hold the temporary variables and parameters of each function. Overrunning this memory leads to a problem called stack overflow.
What happens next is up to the operating system on your computer. If your operating system is robust and the memory management is well controlled, the operating system will stop your program, and report an error (e.g., "Would you like to send a message to Microsoft?"). If your operating system is not as up to par on memory management, you will probably lock up the computer, and/or corrupt other memory locations where other programs are attempting to operate.
In some cases like this, you will be forced to reboot the computer to get it back to work. It is mostly embarrassing, but it can be a problem if you had another program running, and you had not saved your data . . .
The End of Repetition
This was the last topic in the set of repetition topics, and this one was dedicated to recursion. Recursion is a fairly simple process, but as you observed it can do some pretty powerful things with some pretty simple code. Like any other tool you learn about, you should use it when it is appropriate. You will have other opportunities to use recursion later, but this is only provided for your reference as a basic introduction to recursion.