COMP15 Spring 2018
Data Structures
Last updated January 09, 2018 14:40:26 EST
A definition is recursive if it refers to
itself. A recursive function calls itself. A recursive
structure contains components that are the same as the
structure being defined.
It can seem mind bending at first. But recursion is the
Popeye's spinach of procedural abstraction — learn to use
it, and you become a powerful problem solver.
There is no magic. When you call a function, the programming
language implementation doesn't care whether that function is
one you're executing or another one. The exact same thing
happens no matter what (find the function, evaluate arguments, make
stack frame, etc.).
Recursion comes about as a special case of Big Idea #3:
Divide-Conquer-Glue. You take a problem and divide it up into
smaller problems, one or more of which looks like a smaller
version of the original problem. Picture nested matryoshka
dolls.
When you write or try to write or understand a recursive
function you must:
- Identify one or more base cases where the
answer can be computed immediately. These cases are are where the
repetition stops.
- Identify one or more recursive cases where you
can break a problem into pieces that look like smaller versions of
the original problem. These smaller problems are solved using
recursive calls and then are glued together. Some aspect of the
problem must get smaller with each recursive call.
Example Recursive Functions
Consdider the problem of automating the NASA's launch count down
sequence :
void count_down(int n)
{
if (n == 0)
cout << "Blastoff!\n";
else {
cout << "n\n";
count_down(n - 1);
}
}
In this case, we broke the problem of counting down from
some n into two cases. If n is 0, we know what to
do: Blastoff! If not, then we can call out n, but we
still have the problem of counting down
from n - 1. That subproblem looks like the
original problem, but slightly smaller.
A classic example: compute the factorial of a number.
The factorial of the non-negative
integer n is:
- 1, if n = 0
- 1 × 2 × … n, otherwise
int factorial(int n)
{
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
Two ways to think about functions
- the mechanical view of a function
- locate the appropriate function object
- evaluate the arguments expressions left-to-right
- create an activation record (stack frame) for the function
- assign the values of the arguments to the parameters
- execute the body of the function
- save the return value (if any) and recycle the
activation record
- replace the original function call with the return value
- pick up where you left off
- abstract view of a function (like mathematical induction):
- Define behavior/value for simplest/smallest cases.
- Assume that the function works according to its interface
(inputs, preconditions, side-effects, postconditions, return
value) for smaller versions of the problem and figure
out how to make a solution for the slightly larger version.
- Don't think about how it works
- Don't follow the flow of execution
To write a recursive solution to a problem, you will need to
shift back and forth betwen different levels of abstraction:
your code will be both an implementation of the solution, and a
client of the solution.
- Start by thinking through examples. Look at particular
inputs/configurations and write down what the appropriate
output or ending configurations should be. Don't forget
to consider degenerate cases (values including 0, empty
strings/lists/...). Pictures are good.
- Identify one or more base cases (students
usually start by having too many base cases, but see
below). These are circumstances under which no recursive
steps need be taken. Identify solutions for each base
case.
- In the general, or recursive cases,
we will need to divide the problem into pieces. One or
more pieces will look like the original problem.
When figuring out how to decompose the general case
problems, you'll have to figure out what unit of work to
do at a time, ie, how much work each invocation of the
function will perform, and how much will be left for the
recursive invocations. This can be very tricky, and
inexperience with abstractions makes beginning programmers
think too far ahead (both in the general and base cases).
Typically, you'll want to take a small bite out of the
problem in each invocation. For example, in a linked list
application, you'll typically deal with only one list
element at a time, using recursion for the entire rest of
the list. Following the structure of data is often a good
way to start.
- Shift to client mode and assume that the function
works on the recursive subproblem. This is often called
the “recursive leap of faith.” Make the
recursive calls, and then assume the smaller problems
have been solved.
- Figure out what to do with the bit of the problem
you're not passing on to recursive calls.
- Glue the results from the previous two steps together.
Laney Strange
Last updated January 09, 2018 14:40:26 EST