Why are we talking about recursion in a data structures class?
- Recursion is implemented using a data structure we have studied.
- More importantly, recursion is used to define other data structures we
will study, and the algorithms for manipulating them.
- Definitions:
- Recursion is used to define infinite sets with a finite description.
Example: defining the set of natural numbers. Recursive definitions can
be used to both generate and test elements of the set.
- Indefinite repetition:
- Recursion is used to do something an indefinite number of times without
resorting to iteration constructs such as for or
while loops. Example: computing the factorial of a number.
These two uses are closely related.
Recursive definitions reference themselves, either directly or indirectly.
Recursive definitions always include:
- Anchor, Base or Ground Case(s): Simple case(s) that can be handled
without resort to recursion.
- Recursive Relation or Rules:
- Rules that inductively define complex cases in terms of simpler ones.
This is an example of defining an infinite set.
- Ground Case: 0 is a natural number.
- Recursive Relation:
- If n is a natural number, then n+1 is a natural
number.
We can generate the natural numbers by starting with the ground
case, 0, and applying the recursive rule to 0 and to each
newly generated element.
0
1 (from 0 + 1)
2 (from 1 + 1)
3 (from 2 + 1) ... etc.
We
can test whether a number is a natural number by showing that it is
possible to generate the number:
4 is a natural number because 4 = 3 + 1 and
3 is a natural number because 3 = 2 + 1 and
2 is a natural number because 2 = 1 + 1 and
1 is a natural number because 1 = 0 + 1 and
0 is a natural number by definition.
This example shows a recursive definition of a function on an infinite domain
(or equivalently, of an infinite set of pairs).
The factorial of a number n is the product of all integers from 1 to
n (i.e., 1 * 2 * ... * n-1 * n ). The factorial of
0 is defined to be 1.
- Ground Case: The factorial of 0 is 1.
- Recursive Relation: The factorial of n is n
times the factorial of n-1.
Later we see how this definition can be used to compute the factorial,
using recursion instead of iteration.
Recursion involves a different way to think about problems: a problem is
decomposed into simpler problems until it is trivially solvable.
There is nothing mysterious about recursion. We use function calls to
accomplish various things, and it is no different if what we want to accomplish
happens to be handled by the function that we are writing. We just need to be
sure that the recursion terminates!
Here is a general approach to solving a problem recursively:
- Decompose the problem: Identify how you can break the problem into
simpler problems of the same type. In other words, identify the recursive
relation.
- Compose solutions to simpler problems: Assume that you
could solve simpler versions of the same problem. (This is the part students
find mysterious.) Then figure out how to put those solutions together into a
solution to the original problem.
- Solve the simplest problem: Identify the ground case and specify
its solution nonrecursively.
- Decompose the problem: The factorial operates on integers. We can
make a problem involving integers smaller (simpler) by subtracting 1.
The factorial of n-1 is simpler because it involves multiplying one
less integer.
- Compose solutions to simpler problems: If we assume we have the
solution to factorial(n-1) we can get the solution to
factorial(n) by multiplying by n.
- Solve the simplest problem: By definition, factorial(0) =
1.
A straightforward translation of the abstract definition of Factorial:
int Factorial (int n) {
if (n ==0)return 1;
else return n * Factorial (n - 1);
}
We will write recursive definitions for these in class.
- Count ( e list):
- returns the number of times e occurs in list.
- Decompose:
- Compose:
- Base Case:
- Reverse (list):
- returns reversed list.
- Decompose:
- Compose:
- Base Case:
void Reverse () {
char ch;
cin.get(ch);
if (ch != '\n\') {
Reverse();
cout.put(ch);
}
}
In the above definition, Factorial(n) calls
Factorial(n-1). Suppose we allocated a single memory location for
n. What would go wrong?
How does the compiler arrange to keep track of the value of n?
Whenever a new function is called we need to keep track of
- Values for parameters to the function (or locations if call by
reference).
- Values for local variables.
- Return address where execution continues in caller after return.
The compiler could permanently allocate memory for all these items for
each defined function. Why is this a bad idea?
It is inefficient, and it does not support recursion. Instead, the compiler
arranges to dynamically allocate the memory needed to store this
information. New memory is allocated temporarily when a function is called, and
released when it returns.
What data structure is appropriate for organizing this dynamically
allocated memory?
The answer is clear if we consider the fact that the most recent function will
always exit before its caller exits. In other words, last in, first out.
The compiler arranges to store the information on a runtime stack.
Each function's record on the stack is called an activation record or
stack frame.
In addition to storing the information listed in the previous section
(parameters, local values, and return address), each activation record also has
the following.
- Pointer to caller's activation record (why?)
- Location for storing returned value.
The returned value is stacked first, before the rest of the activation
record, so it will be available to the caller after the function exits. (When
the stack is popped, the "top" pointer is updated to "remove" the stack frame
from the logical stack, but it is still there physically long enough to use in
the calling function.)
Now we can see that when a function calls itself, it does not write over its
own values. Each call produces a different instantiation of the
function. (Will diagram example in class, similar to section 5.3.)
A tail recursive function is a recursive function in which the
recursive call is the last statement executed in the function (if it is
executed at all). For example:
void CountDownRecursive (int i) {
if (i >= 0) {
cout << i << ' ';
CountDownRecursive(i - 1);
}
}
The
information in the activation record for the current call is not needed when
the recursive call is made. Thus it can be written over in the recursive call,
saving memory.
It is straightforward to rewrite tail recursive code as a loop. For example:
void CountDownIterative (int i) {
for ( ; i >= 0; i--)
cout << i << ' ';
}
This
leads the textbook author to say that there is no advantage of tail recursion
in C++. However ...
A good compiler can translate tail recursive code into iterative code. (Many
Lisp compilers do this.) With such a compiler, there is an advantage
to using tail recursion for some functions. Recursive definitions are sometimes
much clearer than iterative ones. However recursive calls are more expensive
than iteration. With tail recursion we can have readable recursive code and an
efficient iterative implementation at the same time.
The Reverse function provides an example of a function that is not
tail recursive.
void Reverse () {
char ch;
cin.get(ch);
if (ch != '\n\') {
Reverse();
cout.put(ch);
}
}
(Time permitting, we will trace the execution of this to see why it
works.)
Definitions that are inherently non-tail recursive are more difficult to write
iteratively. This is because one must implement an explicit stack to do the job
that the runtime stack did in the recursive form. For example, using an array:
void IterativeReverse() {
char stack[80];
register int top = 0;
cin.get(stack[top]);
while(stack[top] != '\n')
cin.get(stack{++top]);
for (top -= 2; top >= 0; cout.put(stack[top--]));
}
or
using a stack ADT:
void IterativeReverse2() {
int ch;
stack.Clear();
cin.get(ch);
while (ch != '\n') {
stack.Push(ch);
cin.get(ch);
}
while (!stack.IsEmpty())
cout.put(stack.Pop());
}
In
C++ the IterativeReverse implementation is the most efficient, but is more
difficult to understand and maintain than the recursive one.
Functions can be recursive (call themselves) indirectly, that is via other
functions: f can call g which calls f. An
example is parsing expressions. Suppose you have a parser for each type of
subexpression, and have an expression "3 + (2 * (4 + 4))". The
function that processes "+" expressions would call that for
"*", which in turn would call the first.
A recursive call can also be given an argument which includes another recursive
call. An example is Ackermann's function, a function that grows horrendeously
fast. (For example, A(4,1) far exceeds the estimated number of atoms
in the universe.)
A(n,m) = m+1 if n = 0
A(n-1,m) if n > 0 and m = 0
A(n-1, A(n,m-1)) otherwise.
This
is an example of a function that is much easier to write recursively: It has
been proven that no equivalent definitions using arithmetical operators +, -,
*, /, and ^ exits. Unfortunately a straightforward recursive computation is not
even O(2^n) in time or space.
Nested recursion is a special kind of double recursion, where
a recursive definition refers to itself more than once.
Sometimes a straightforward recursive definition is inefficient in ways that
can be avoided (unlike Ackerman's function).
The Fibonacci numbers are a sequence of numbers where the nth number
in the sequence is defined as follows:
Fib(n) = n if n < 2.
Fib(n-2) + Fib(n-1) otherwise.
This
definition can be written in C++ as follows:
int Fib (int n) {
if (n < 2)
return n;
else
return Fib(n-2) + Fib(n-1);
}
This definition is very inefficient. (In class we'll make this point with
figure 5.6 from the text.) A more efficient iterative definition is:
int InterativeFib (int n) {
if (n < 2)
return n;
else {
register int i = 2, tmp, current = 1, last = 0;
for ( ; i <= n; ++i) {
tmp = current;
current += last;
last = tmp;
}
return current;
}
}
(A register declaration tells the compiler that the variables
will be heavily used, so should be allocated in registers if possible.)
Sometimes
there are different ways to write recursive definitions, one being more
efficient than the other. This is the point of the extra credit problem
in the homework.
Recursion makes it easy to implement problem solving techniques in which one
searches for possible solutions and backtracks when an
attempted solution fails to work out.
The solution to many problems consist of a number of interacting (mutually
dependent) choices. Some example problems include:
- The 8-queens problem described in the text.
- Deciding what move to make in Chess.
- Parsing sentences or expressions in an ambiguous language. "The horse
raced past the barn fell."
- Planning a sequence of actions to achieve a goal.
- Traveling salesman problem: visiting cities in an order that minimizes
distance.
Some choices made early during problem solving might not be compatible
with other choices made later. When this happens it may be necessary to back up
to the earlier choice point and try another option (for example, place the
first queen on a different square; consider a different move in Chess; assign a
word or sentence constituent to a different syntactic category; go to a
different city first).
Backtracking is this process of backing up and trying other choices.
It is easily implemented with recursion because:
- The run-time stack takes care of keeping track of the choices that got us
to a given point and the remaining alternatives
- Upon failure we can get to the previous choice point simply by returning a
failure code from the recursive call.
I will illustrate the general idea of backtracking by demonstrating the
execution sequence on the 8 Queens problem. We will not have time to go into
detail on this, so please read the text.
Due Feb. 24th (which is also exam day).
1. Problem 1 of page 131.
2. Problem 2 of page 131. You may write pseudocode, C++, or another language.
3. Problems 3 and 4 of page 131.
(A static variable is allocated just one permanent location in memory,
i.e., is not on the runtime stack. Hence the same memory location is used each call.)
Use the input line "abc\n" (that's the character a, followed by b, followed by c, and a newline). In addition to the information asked for
in the textbook, write a paragraph comparing the results of problems 3 and 4,
and indicating the significance.
4. Problem 9 of page 133. The "binomial coefficient" gives the number
of combinations of n things chosen k at a time. You may
write pseudocode, C++, or another language.
About "n choose k" notation. In case you are not familiar with the notation
of problem #9 page 133 (our problem 4 of HW 3): The parentheses with an "n" on
top and a "k" on the bottom stands for a number -- in particular the number of
different ways in which you can choose k things out of a set of n things.
Your job is to write a recursive function that computes this number. n and k
will be the two arguments to the function.
Example: 3 things {a, b, c}, taken 2 at a time: there are 3 ways to do it: {a,
b}, {a, c}, {b, c}. (Order does not matter.)
Try drawing the recursive call tree for this computation. If your function is BC then
->BC(3,2)
--->BC(2,1)
----->BC(1,0)
<-----1
----->BC(1,1)
<-----1
<---2
--->BC(2,2)
<---1
<-3
Extra credit: Do 18 p. 133, writing the program.
Dr. Daniel Suthers
Learning Research & Development Center
University of Pittsburgh
3939 O'Hara Street
Pittsburgh, PA 15260
(412) 624-7036 voice
(412) 624-9149 fax
suthers+@pitt.edu
http://www.pitt.edu/~suthers/
Last modified: Fri Feb 21 16:17:31 1997