Recursion Notes

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.  (which should not be a huge stretch of anyone's imagination)  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 method to fix this problem.  It could look like this:

public 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
public 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 methods.  
For example, the following for loop will count up the number of times that 'a' occurs in a String, you can rewrite it quite easily as a recursive method:

int count = 0;
for (int b = 0; b < str.length(); b++)
    if (str.substring(b,b+1).equals("a") count++;

the recursive version would be as follows (assuming that position and count starts at 0)

public static int counta(int position, String str, int count) {
    if (position == str.length()) return count;
    else if (str.substring(a,a+1).equals("a")) {
        return counta(position+1, str, count + 1);
        }
    else return 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.
An issue we've been skirting around has been the issue of the fact that there are two major forms of recursion.  For the AP it appears that you will not need to be able to identify which is which, or code them one way or another (at least they won't EXPLICITLY require you to do so), but it is still very very useful for you to know the beast (recursion) as best as you can in order to be as prepared for this exam as you possibly can.  (and you know, for educational reasons as well)

Embedded Recursion:
    Embedded recursion is the form of recursion where the result is computed within the return statement, and thus you can't figure out what the answer is until the very end when all of the recursive calls are unfolded.  An example of code that works that way is as follows:
(the stupid adder example)
int stupidadd(int a, int b) {
    if (a == 1) return 1 + b;
    else return 1+stupidadd(a-1, b);
}

if we were to run this with an input of 3, 4 the program would first try to figure out what stupidadd (sa for short) (3,4) is

since 3 is not 4, it would say "ah, it's the same as 1+sa(2,4)
the problem is it doesn't know what sa(2,4) is so it holds back the 1, and figures out what sa(2,4) is.  2 is not 1, so it knows that sa(2,4) is the same as 1+sa(1,4), but it doesn't know what sa(1,4) is. So then it realizes that 1 IS the same as 1 (clever, ain't it?) and thus sa(1,4) is 5, once it knows that, it realizes that sa(2,4) is 1+ 5 or 6, and thus sa(3,4) is 1+6 or 7, and thus at the VERY END it can figure out things.  
The point of this is that until the very end, you have no idea what the answer is.  This is probably the purer form of recursion, and it has some advantages, for instance, you can have a recursive step with many calls back to the method in question.  (for instance, return fibonacci(n-1)+fibonacci(n-2))

Tail recursion:
The other form of Recursion is called tail recursion.  This is perhaps a little more comfortable for you as it doesn't have the magical step in which you say you want to return the value of the recursive call as the value of the current call.  (return fibonacci(n-1)+fibonacci(n-2) as the return value of fibonacci(n))  Under this form you add an extra argument to help you build up the final result as you go along.  This gives you the advantage of always knowing what the current answer is.  For instance, the above stupidadder would be written as follows as a tail recursive method:
// precondition: result = 0
int stupidadd(int a, int b, int result) {
    if (a == 1) return result + 1 + b; // yes, this is a violation of how the stupidadder is supposed to work
    else {
    result += 1;
    return stupidadd(a-1, b, result);
    }
}

However, there is one sort of catch with tail recursion: it adds an extra parameter...

Sometimes in life (and on the AP or my classwork) they will demand you write a method that must fit a particular prototype and you realize you can't get your tail recursive (or embedded recursive) method working with only those parameters... but if you had an extra one it would be a cinch.

In those cases, unless told otherwise, you can just write another method!  Let's say for the stupidadder method one were to require you to have it match this format:
int sa(int a, int b);

well you could always write a new method like this:

int sa(int a, int b) {
    int result = 0;
    return stupidadd(a, b, result);
}

This new method is called a helper method.  In this case it helps you write the kind of method you want to.  (assuming you prefer tail recursion)

For most cases, you should code whichever you feel more comfortable with.