Chapter 8f

Looping Without Loops - Recursion


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Introduction

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. We will be using recursion in class, albeit in a limited way. The goal is to give you an introduction to this interesting process that you will continue using in later courses.

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.

cout "Enter a sentence that ends with a period: "; reverseSentence();

Now, consider the function that is called.

void reverseSentence() { char oneChar; cin >> oneChar; if( oneChar != PERIOD ) { reverseSentence(); } cout << 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.

Now, 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

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.

  1. there is some base case, or original case where the function takes a simple action

  2. there is some generalized case that looks like a smaller version of the base case

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 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 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 number

Now then, the code would be just as simple. Note this uses the long data type, which handles longer than normal integers.

long factorial( long number ) { if( number <= 1 ) { return 1; } else { return number * factorial( number - 1 ); } }

Consider the following graphic.

Factorial Graphic

The above graphical presentation is actually a very effective way for you to analyze the results of a recursive process. 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.

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

int number, counter = 1; long result = 1; cout "Enter number: "; cin >> number; while( counter <= number ) { result *= counter; 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 actual code for this is actually this simple, but it involves testing for locations inside the flood area, so this activity will be left for later work. Nevertheless, without consideration for locations of empty and painted areas, which are pretty easy to identify, recursion can make a complicated task pretty easy.

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 in this course. Other than conducting your own experiments, do not use recursion for assignments or assessments in this course.

Topic Summary