Fall 2000
Lecturer: Carl Sable
Topic #13: Recursion
Informally speaking, a recursive function is a function that calls itself. Recursive functions can be used to solve problems that are very difficult to solve without recursion.
First, we are going to look at a couple of mathematical problems that can be solved with recursion. These are two very common examples of recursion, although the first can be solved a bit more efficiently without recursion, and the second can be solved much more efficiently without recursion. None-the-less, they are simple examples that help to explain the concept, so we will start with them anyway.
First, let's look at a function that takes, as input, an integer parameter "n", assumed to be non-negative, and returns "n" factorial (n!).
int factorial(int n)
{
if (n == 0)
return 1;
else
return n*factorial(n-1);
}
What is going on here? The function "factorial" takes an integer "n" as a parameter. If the integer is 0, it simply returns 0 factorial which is defined to be 1. For higher values of "n", it uses the equation "n! = n*(n-1)!". The function "factorial" makes a recursive call to itself to compute "(n-1)!", then multiples the value returned by this call by "n", and this is the value returned by the current call to the function.
Let's say that in another function, we have the following statement:
printf("3! = %d.\n", factorial(3));
What happens? The function "factorial" gets called with "n" initialized to 3. Since "n" does not equal 0, we go to the "else" clause of the "if" statement in the function. This says to return the value of "3*factorial(2)". So we make another call to "factorial", but this time "n" is initialized to 2. Since "n" does not equal 0, we go to the "else" clause again, which says to return "2 * factorial(1)". This call to "factorial" will return "1*factorial(0)". This causes a call to "factorial" with "n" initialized to 0, and this final call to "factorial" will return a value of 1. Afterwards, the previous call to "factorial" (which had "n" initialized to 1) will return "1*1" which is still 1. Then the previous call to "factorial" will return "2*1" which is 2, and finally the original call to "factorial" will return "3*2" which is 6. Remember that when one function calls another, the calling function does not continue until the called function finishes executing. This is also true when a function calls itself!
What would happen if we forgot the "if" statement, and simple had the function defined as follows:
int factorial(int n)
{
return
n*factorial(n-1);
}
This would cause infinite recursion, which is similar to an infinite loop. Each call to "factorial" would result in another call to "factorial", and the program would never end. Eventually it would run out of memory (every call to a function requires some memory), and the program will crash, but you will probably wind up hitting Ctrl-C to halt the program before this happens.
Every useful recursive function has a base case and a general case. The base case returns a solution for the given input parameters without doing a recursive call. The general case either breaks a problem into parts, each of which is solved with a recursive call, or expresses the solution to the given problem in terms of the solution to another problem involving a recursive call.
Of course, recursion is not necessary to solve the factorial problem. It could have been solved iteratively with a simple loop as follows:
int factorial(int n)
{
int result =
1;
while (n
> 0)
{
result = result *
n;
n = n - 1;
}
return
result;
}
This is pretty straightforward. The function factorial takes an integer "n" as a parameter, starts "result" as 1, and multiplies "result" by all the integers from 1 to "n".
Which solution is better? Some would say that the recursive solution is more elegant, and maybe even simpler to understand or implement, but it is actually less efficient. The reason is that every call to a function requires memory. The program must record where the called function is being called from and remember the values of all local variables and parameters of the calling function. If you call the recursive version of "factorial" with a large number, there will be this many calls to the function all active at one time, so if the original value of "n" is x, there will be x copies of all information necessary to implement the function "factorial" all active in memory at one time! This can cause memory problems, and also might cause your program to run slower to handle the bookkeeping necessary for each function call.
Now let's look at the Fibonacci series. The first two numbers are defined to be 1 and 1, and then every new number is computed by adding together the two previous numbers. The first several numbers are therefore:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Let's look at a recursive function that computes and returns the nth Fibonacci number:
int Fibonacci(int n)
{
if (n <=
2)
return 1;
else
return (Fibonacci(n-1) +
Fibonacci(n-2));
}
This is pretty straight-forward and elegant looking and it hardly has to be explained.
Now let's look at a non-recursive version:
int Fibonacci(int n)
{
int prev1 =
1, prev2 = 1;
int x, cur;
if (n <=
2)
return 1;
else
{
for (x = 3; x <= n; x++, prev2 =
prev1, prev1 = cur)
{
cur
= prev2 + prev1;
}
return cur;
}
}
So, if "n" is less than or equal to 2, we're still just returning 1, there's nothing to compute. Otherwise, we loop from 3 to "n". For each iteration of the loop, we sum the two previous values and store the result in "cur". After each iteration, we update the two previous values. "prev2" takes the value of "prev1" and "prev1" takes the value of "cur".
This looks more complex than the recursive version, but it is actually significantly more efficient, and the difference in efficiency is much more extreme than with the factorial example. Why?
Consider a call to the recursive function to compute "Fibonacci(5)". We have:
Fibonacci(5) = Fibonacci(4) + Fibonacci(3).
This does two recursive calls. For the first, we compute:
Fibonacci(4) = Fibonacci(3) + Fibonacci(2)
For the second, we compute:
Fibonacci(3) = Fibonacci(2) + Fibonacci(1).
All together, we are actually therefore saying:
Fibonacci(5) = Fibonacci(3) + Fibonacci(2) + Fibonacci(2) +
Fibonacci(1).
Note that we are going to call the "Fibonacci" function multiple times with the same parameter! We are therefore repeating work multiple times! In fact, if we call Fibonacci with a large number "n", we going to wind up making on the order of "2^n" calls to the function! We are dealing with an exponential solution instead of a linear one! This is a terrible slow down, and the recursive solution for "Fibonacci", however elegant it looks and as simple it is to code, is a bad idea (unless you are absolutely sure it will only be called with low valued parameters)!
Let's look at an example of a mathematical function in which recursion is more useful. Consider the function defined as follows:
F(n) = 2 if n is 1, otherwise F(n) = F(n/2) + 5.
We are assuming that "n/2" is integer division, and the fractional part is truncated if "n" is odd. We will also assume that "n" is positive.
Here is the recursive solution:
int F(int n)
{
if (n == 1)
return 2;
else
{
return (F(n/2) + 5);
}
}
That is pretty straight forward. Why can't we do a more efficient iterative (non-recursive) solution? The problem is that we would have to compute all values of "F" starting at "F(1)" and looping up to "F(n)". With the recursive solution, we are computing only the order of "log n" values of "F(n)". Furthermore, if we want to do an iterative solution, we have to store all these previous values of "F(n)" as we go along, but if we don't know the maximum possible value of "n", this means we have to use dynamic memory allocation. (I just made this function up, and it is possible that there is some way to "solve" the formula to compute each a value of "F(n)" with some simple formula that involves neither recursion or a loop, but unless the programmer can figure out how to do this, recursion is probably the best and easiest way to implement it.)
Recursion gets more fun when we look at other non-mathematical things we can do with it. One popular example deals with the Towers of Hanoi puzzle. You have three needles that can hold disks; namely, a source needle, a destination needle, and an auxiliary needle in between. You start with all the disks on the source needle in size order, with the largest on the bottom and the smallest on top. You are allowed to move one disk at a time from one needle to another, subject to the constraint that no disk is ever on top of a disk smaller than itself.
Let's say you want to write a function that tells you each move, in order, to move the pile from needle A (the source needle) to needle C (the destination needle), with the auxiliary needle named needle B. This can be done with a recursive function quite simply. In order to move a pile with "n" disks from A to C, you have to first move a pile with "n-1" disks (all but the bottom disk of the original pile) from A to B, then move the largest disk from A to C, then move the pile with "n-1" disks from B to C.
The function might look like this:
void Tower(int n, char source, char dest, char aux)
{
if (n == 1)
printf("Move from %c to
%c.\n", source, dest);
else
{
Tower(n-1, source, aux, dest);
printf("Move from %c to
%c.\n", source, dest);
Tower(n-1, aux, dest, source);
}
return;
}
Let's say another function has the following call to this function:
Tower(4, 'A', 'C', 'B');
This will display the following to standard output:
Move from A to B.
Move from A to C.
Move from B to C.
Move from A to B.
Move from C to A.
Move from C to B.
Move from A to B.
Move from A to C.
Move from B to C.
Move from B to A.
Move from C to A.
Move from B to C.
Move from A to B.
Move from A to C.
Move from B to C.
If you go through the steps, you will find that this correctly moves a pile with four disks from needle A to needle C.
One thing that recursion is often used for is game playing. Let's say you wanted to rewrite the Tic-Tac-Toe program examined earlier, but you wanted the program to play perfectly by looking ahead enough moves such that it would always force a win when it could and would never lose if it didn't have to. One way to do this is to consider a recursive search through a game tree.
Consider a node at the top of a tree (the root of a tree) to represent the current state of the Tic-Tac-Toe game. For each possible move that the current player can make, there is a child of this node representing the state of the game that would result if the move is made. For each of these nodes, there is also one child for each possible move that might be made from there. Etc. The leaves of the node represent positions in which the game is over, either because one player has won or because the game has ended in a draw. A recursive routine to choose the computer's move would recursively look at each possible move it could make, calling itself for each such state as if it were the opponent, assuming that the opponent will use the same "perfect" strategy as it does. If at any time, a player can take a move that will result in a win, it is assumed that the player will do that. At the same time, it is assumed that a player will never choose a move that results in a loss unless it has to. Values of leaf nodes might be 1 if the computer wins, -1 if the opponent of the computer wins, and 0 if the game is a draw. Values of inner nodes are assigned one of these values depending on what state will result if both players play perfectly. Of course, it is well-known that when both players play perfectly, the game ends in a draw, so if the root of the tree is the opening position of a game, it will be given the value of 0 after a full recursive search through the tree.
Things get more complicated when you are dealing with a game like Checkers or Chess, in which the game tree is too big to traverse completely. (It has been said that a computer the size of the earth and the age of the universe running as fast as possible according to laws of quantum physics would be about 10% done with looking at all possible Chess games!) What you therefore do instead is have some heuristic function that can examine a board without looking ahead and give it a value. Then, given a starting node (the current game position), when it is the computer's turn, it looks ahead some fixed number of levels down the tree. When it gets this far down, it uses the heuristic function to compute the value of the current node, and these values are used to form values for nodes above them. The single current move leading to the node with the best value of the possible choices is chosen as the computer's move.
Let's say that you want to write a program to compute the values of arithmetic expressions. Assume you have a function that works for expressions which do not contain parentheses, just simple expressions containing arithmetic operators like '+', '-', '*', and '-'. It shouldn't be too hard to update such a function to handle parentheses. When you see a left parenthesis, just recursively call the routine to handle the part of the expression within the parentheses, and then continue treating the return value of the recursive call as if it were a number directly in the expression.
Of course, coding these solutions might still be somewhat of a challenge, but it would probably be much harder to code them without using recursion!