Aim for FiveComputer Science A

Unit 4 · Topic 4.16

4.16 Recursion

A recursive method solves a problem by calling itself on a smaller version of the same problem. On the exam you trace recursive methods to find what they return or print; you won't write one. This topic covers base cases, recursive calls, the call stack and a reliable way to trace.

Key terms

  • recursion
  • base case
  • recursive call
  • call stack
  • tracing

The two parts of a recursive method

A recursive method is a method that calls itself. Every one needs at least one base case, a condition where the method returns without calling itself, which stops the recursion. It also needs at least one recursive call, where the method calls itself with arguments that move closer to the base case.

public static int addDown(int n) { if (n <= 1) { return n; } return n + addDown(n - 2); }

Here the base case is n <= 1, and each recursive call passes n - 2, which gets smaller every time. addDown(7) is 7 + 5 + 3 + 1 = 16.

If the arguments never reach a base case, the method keeps calling itself until Java runs out of memory for calls and throws a StackOverflowError. That's the recursive version of an infinite loop.

Each call has its own variables

Every call to a method gets its own fresh set of parameters and local variables. When addDown(7) calls addDown(5), the new call has its own n, equal to 5, while the first call's n is still 7, waiting.

The parameter values track the progress of the recursion, the way a loop control variable tracks a loop's progress. Java keeps the waiting calls on the call stack. Each call stays paused until the call it made returns, then picks up exactly where it left off.

Recursion and loops

Recursion is another form of repetition. Anything you can do with recursion, you can do with a loop, and the other way around. This loop gives the same results as addDown:

public static int addDownLoop(int n) { int total = 0; while (n > 1) { total += n; n -= 2; } return total + n; }

How to trace

Write each call on its own line, going down until you hit the base case. Then go back up, filling in each return value from the bottom. Don't try to finish the top call first: it can't finish until everything below it has returned.

Pay attention to where any print statements are. Code before the recursive call runs on the way down, in order. Code after the recursive call runs on the way back up, in reverse order.

Not on the exam

Writing recursive code isn't tested. Spend your practice time tracing.

Worked examples

Try each one yourself first, then open the solution.

  1. Example 1

    Tracing return values

    What does mystery(4072) return?public static int mystery(int n) { if (n < 10) { return n; } return mystery(n / 10) + n % 10; }

    Show the solution
    1. Step 1: Going down: mystery(4072) calls mystery(407), which calls mystery(40), which calls mystery(4).
    2. Step 2: mystery(4): 4 is less than 10, the base case, so it returns 4.
    3. Step 3: Back up: mystery(40) returns 4 + 40 % 10, which is 4 + 0 = 4.
    4. Step 4: mystery(407) returns 4 + 407 % 10, which is 4 + 7 = 11.
    5. Step 5: mystery(4072) returns 11 + 4072 % 10, which is 11 + 2 = 13. The method adds up the digits.

    Answer: It returns 13.

  2. Example 2

    Printing on the way down and up

    What does echo(3) print?public static void echo(int n) { if (n > 0) { System.out.print(n + " "); echo(n - 1); System.out.print(n + " "); } }

    Show the solution
    1. Step 1: echo(3) prints 3 , then calls echo(2) and waits.
    2. Step 2: echo(2) prints 2 , then calls echo(1). echo(1) prints 1 , then calls echo(0).
    3. Step 3: echo(0): 0 > 0 is false, so it does nothing and returns. That's the base case.
    4. Step 4: Now the waiting calls finish, newest first. echo(1) prints its second 1 , then echo(2) prints 2 , then echo(3) prints 3 .

    Answer: It prints 3 2 1 1 2 3 .

Common mistakes

  • Trying to finish the first call before the deeper calls return. Work down to the base case, then back up.
  • Forgetting that code after a recursive call runs later, in reverse order.
  • Thinking all the calls share one n. Each call has its own copy of every parameter and local variable.

On the exam

  • Expect multiple-choice questions where you trace a short recursive method. Write out the chain of calls; it's slower than guessing but much more reliable.

Connected topics

Videos

Check yourself

4 questions on 4.16 Recursion. Pick an answer to see if you got it, and why.

Question 1 of 4

Consider the following method.public static int product(int n) { if (n <= 1) { return 1; } return n * product(n - 2); }What value is returned by the call product(7)?

Question 2 of 4

Consider the following methods.public static void countUp(int n) { if (n > 0) { countUp(n - 1); System.out.print(n); } } public static void countDown(int n) { if (n > 0) { System.out.print(n); countDown(n - 1); } }What is printed as a result of the calls countUp(3); followed by countDown(3);?

Question 3 of 4

Consider the following method.public static int f(int n) { if (n < 2) { return n; } return f(n - 1) + f(n - 2); }What value is returned by the call f(6)?

Question 4 of 4

Consider the following method.public static int shrink(int n) { if (n == 0) { return 0; } return 1 + shrink(n - 2); }Which of the following best describes the result of the call shrink(5)?

0 of 4 answered