March 13 notes for Computer Science AP (Recursion Lecture #1)
Recursion in its simplest form means solving a problem by repeating a
process until the answer is found. A possible analog is if you
are trying to figure out where you left your car keys, you can work by
tracing your steps backward. You can work like this:
Step 1 - Where was I 10 minutes ago?
Step 2- Did I have my keys?
Step 3- If I did, I know where they are now, if I didn't, I need to
look 10 minutes further back, and go back to Step 1
This will continue until you figure out where you found your keys (very
hopefully)
Computers are somewhat the same in that a similiar principle is at
play.
Let me give a very very simple example:
Let us imagine that computers could not add well. Let us say that
for some odd reason they could not add more than 1 to any given number
at any given time, meaning that they could figure out what 1 + 7 is,
but not what 4+4 was. In this bizarro world, you could help
yourself by writing a recursive function to fix this problem. It
could look like this:
int fixadd(int a, int b) {
if (a = 1) return 1+b;
else return 1 + fixadd(a - 1, b);
}
What this is saying is if we're dealing with a situation we know about
for sure (adding 1 to a number), we can just do that and be done,
otherwise, we need to get closer to the situation we know about (by
making a one less), and adding 1 to the front. We're using the
mathematical princple that a+b = 1+(a-1)+b
This illustrates the basic principles of recursion:
A) You need a stop condition. This is also
often called a base case. This is a situation that when reached
you can stop recursing because the problem is very simple at this
point. In this case, this is a situation that our bizarro
computer can handle on its own.
B) You need a recursive step, this is a step designed
to do what work you can in an unknown situation and try to work CLOSER
to the base case. In this case, we're making a 1 less at our
recursive step, and assuming that a starts off as a positive number,
making a 1 less will get us closer.
Let me give a slightly more complicated example:
There is a mathematical series called Fibonacci's Sequence. This
is a number series that starts like this: 1 1 2 3 5 8 13 21 34 and so
forth. You can see that all numbers are simply the sum of the two
that come before it. (as long as the 1st two numbers are 1)
If we wanted to figure out what any value in this series is just by
specifying its position in the series, we could do it as follows.
The base case here could be the simple knowledge that the 1st & 2nd
position in the series must be 1.
The recursive case could be that all other numbers are the same thing
as the sum of the two before it.
So possible code for this can look as follows:
// precondition: assume position is 1 or greater
int fibonacci(int position) {
if (position < 3) return 1;
else return fibonacci(position - 1) +
fibonacci(position - 2);
}
Try running that code!
Finally, you already somewhat know a simplified version of
recursion. Most for loops can be rewritten as recursive
functions.
For example, the following for loop will count up the number of times
that 'a' occurs in an apstring, you can rewrite it quite easily as a
recursive function:
int count = 0;
for (int a = 0; a < str.length(); a++)
if (str[a] == 'a') count++;
the recursive version would be as follows (assuming that position and
count starts at 0)
void counta(int position, apstring &str, int &count) {
if (position == str.length()) return;
else if (str[a]=='a') {
count = count + 1;
counta(position+1, str, count);
}
else counta(position+1, str, count);
}
What this is saying is that if we're at the end of the string, we're
done with work (and we don't want to modify count), otherwise, we want
to see if the character at this position is 'a', if it is we want to
continue running through the string with a count that's one higher,
otherwise we just want to continue running through the string.
Note how at every step we're moving position up 1, thus getting closer
to the base case.