Recursion
A recursive method is a method that solves a small version of its own job directly, and solves every larger version by making the job smaller and calling itself. There is no new language feature involved. It is the method call you already know, used on the method you are already inside.
The 2 parts, and nothing else
Every recursive method you will write has exactly 2 kinds of case in it, and the whole method is deciding which one you are in.
The base case is the version of the job small enough to answer outright, with no further calls. The recursive case makes the job strictly smaller and hands that smaller job to a fresh call of the same method, then does whatever remains once that call comes back.
public static int countDown(int n)
{
if (n == 0) // base case: answer it outright
{
return 0;
}
return 1 + countDown(n - 1); // recursive case: smaller, then finish up
}Two questions decide whether a recursive method is correct, and you can ask both before you run anything. Does every path eventually reach the base case? And is the smaller call actually smaller, every single time? A method that answers yes to both terminates. A method that answers no to either runs until the machine stops it.
Each call is a separate call, with its own copies
This is the part that decides whether the rest of it makes sense, and it is easy to skip past.
When a method calls any method, Java sets aside a small block of memory for that call, called a frame. The frame holds that call's parameters, its local variables, and the place to return to when it finishes. The frames stack up: the newest one on top, the one that called it underneath, all the way down to main. When a call returns, its frame is thrown away and the one underneath picks up where it left off.
A recursive call is not special in any of this. countDown(3) calling countDown(2) makes a second frame with its own n, holding 2, sitting on top of the first frame whose n still holds 3. Neither one can see the other's variables. That is why there is no need for a variable that gets reassigned: each call keeps its own numbers, and the stack of frames is doing the remembering that a loop's variables would have done.
countDown(3) n = 3 waiting
countDown(2) n = 2 waiting
countDown(1) n = 1 waiting
countDown(0) n = 0 returns 0
then 1 + 0, then 1 + 1, then 1 + 2,
on the way back down the stackTrusting the smaller call
The hard part of writing a recursive method is not the syntax. It is being willing to write countDown(n - 1) and treat its answer as correct while you are still in the middle of writing the method that produces it.
Do it anyway, and do it deliberately. Assume the smaller call returns the right answer. Your only job in the recursive case is to say what to do with that answer to get the answer for the size you were handed. Once the base case is right and every recursive case is right with respect to a correct smaller answer, the whole thing is right, because every call is standing on a smaller one and the smallest one is answered outright.
Tracing 20 levels of calls on paper is how people talk themselves out of recursion. Trace 2 levels to check the shape, then check the smallest cases by hand, and stop.
What the official site names
The department's own words for this area:
Simple recursive methods to accomplish a task, which may or may not be list related. Examples would be printing a linked list in reverse, computation of factorials, and other recursive algorithms at the level of those covered in Programming Principles I and II and in Data Structures.
Official site: FAQs About the APE, item 15.
The same site keeps a separate list of problem areas it has seen before, and one line on it belongs to this topic:
Inability to implement simple recursion
Official site: Common Problems.
Read the first quotation for what it does not say. It does not name one data structure, because "may or may not be list related" covers arrays, chains of nodes and plain numbers. It does not ask for anything clever, because "simple" and "at the level of those covered" both point at the material you have already had. The lessons below are the shapes those examples come in.
The lessons
Trace these before you go on
Work each one on paper and write the answer down before you open it.
Using the countDown method above.
countDown(4). How many frames exist at the deepest point, and what does each one'snhold?- What does the call return, and how is that number built?
- Which call returns first, the outer one or the inner one?
- What happens on
countDown(-1)?
Answers
1. Five frames, holding 4, 3, 2, 1 and 0. The frame for main is under all of them.
2. It returns 4. The base case returns 0, and each frame on the way back adds 1 to what it received, 4 times.
3. The inner one. A call cannot finish until the call it is waiting on has finished, so frames come off the stack in the reverse of the order they went on.
4. It never reaches the base case. n is never 0, and every call makes it more negative, so the frames pile up until the machine runs out of room for them and throws a StackOverflowError.
For each one, say whether every path reaches a base case, and if not, what is wrong.
if (n == 0) return 1; return n * factorial(n - 1);called withnequal to 5.- The same method called with
nequal to -3. if (n <= 0) return 1; return n * factorial(n - 1);called withnequal to -3.if (i == array.length) return best; return helper(array, i, Math.max(array[i], best));
Answers
1. Yes. Each call lowers n by 1 and 5 counts down to 0.
2. No. n starts below the base case and moves further from it forever.
3. Yes. The test now catches every value at or below 0, so the first call is already the base case. Widening the base case is the usual repair for 2.
4. No. The base case is written correctly, and the recursive call passes i unchanged, so the problem never gets smaller and the same call repeats forever. The argument has to be i + 1.
These 2 methods both print the numbers involved. Only the order of the 2 statements differs.
public static void up(int n)
{
if (n == 0) { return; }
System.out.println(n);
up(n - 1);
}
public static void down(int n)
{
if (n == 0) { return; }
down(n - 1);
System.out.println(n);
}- What does
up(3)print, in order? - What does
down(3)print, in order? - Explain the difference using the frames, not the code.
Answers
1. 3, 2, 1. Each frame prints before it makes the next call.
2. 1, 2, 3. Each frame makes the next call before it prints anything.
3. In up, the printing happens on the way down the stack, while frames are being created, so the first frame created prints first. In down, every frame is created before anything prints, and the printing happens on the way back up as frames are thrown away, so the deepest frame prints first. This is exactly the trick that prints a linked list backward.
In the practice APE
The Practice APE Exam Instructions put 2 problems under this heading, both on arrays and both in the same folder. findLargest walks an array and returns the largest value in it. reverseArray reverses an array in place. In each one the public method is already written for you and you write the private helper it calls, which is a pattern worth recognizing on sight; it is worked through in Recursion on an array.
Neither one is list related, and the official topic list says the problems may or may not be. Printing a linked list in reverse is the example the list names, so Recursion on a linked list covers it even though the practice set has no problem for it.
The one thing to keep
A recursive method answers the smallest version of its job outright and makes every other version smaller before handing it on. Each call gets its own frame with its own copies of the parameters, which is where the state lives instead of in a reassigned variable. Write the base case first, make sure every path moves toward it, then trust the smaller call and say only what to do with its answer. Check the smallest cases by hand, and do not trace 20 levels to convince yourself.