12.1. Recursion

The AP CS A exam usually has about 4-6 recursion problems. You only need to know how to trace recursive methods (figure out what they return or print). You will not be asked to write a recursive method on the exam.

12.2. What is Recursion?

Recursion is when a method calls itself. See the example method below.

1
2
3
4
5
public static void neverEnd()
{
  System.out.println("This is the method that never ends!");
  neverEnd();
}

This method will print out “This is the method that never ends!” and then call itself, which will print out the message again, and then call itself, and so on. This is called infinite recursion, which is a recursion that never ends. Of course, this particular method is not very useful.

Which line in the method neverEnd (shown above) contains the recursive call (the call to the same method)?

Here is another method that calculates the factorial of a number. The factorial of a number is defined as 1 for 0 and n * factorial (n-1) for any other number.

1
2
3
4
5
6
7
public static int factorial(int n)
{
  if (n == 0)
    return 1;
  else
    return n * factorial(n-1);
}

Which line in the method factorial contains the recursive call (the call to the same method)?

The factorial method has a way to stop. The recursion stops when n is equal to 0.

Note

The thing that stops a recursive method from calling itself is called the base case. A method can have more than one base case (way to stop the recursion).

Check your understanding

    11-1-1: Is the following method recursive?

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public static int mystery()
    {
       int total = 0;
       for (int i=10; i>0; i--)
       {
          total = total + i;
       }
       return total;
    }
    
  • Yes
  • Where is the call to the same method?
  • No
  • There is no call to the same method, so this can not be a recursive method.

    11-1-2: Is the following method recursive?

    1
    2
    3
    4
    5
    public static int mystery2(int x)
    {
       if (x == 1) return 1;
       else return x + mystery2(x-1);
    }
    
  • Yes
  • Yes, any method that contains at least one call to the same method is recursive.
  • No
  • Look again. Check if the method contains a call to itself.

    11-1-3: What is the value of n when this method stops calling itself (when it reaches the base case)?

    1
    2
    3
    4
    5
    6
    7
    public static int product(int n)
    {
       if(n == 1)
          return 1;
       else
          return n * product(n - 2);
    }
    
  • 0
  • Look again. What is the value of n when this method returns a value, without doing a recursive call?
  • 1
  • This method stops calling itself when n equals 1 (line 3).
  • 2
  • Look for a return with a number after it. When is this code executed?

    11-1-4: What is/are the values of the variable bunnies when this method stops calling itself (when it reaches the base case)?

    1
    2
    3
    4
    5
    6
    public static int bunnyEars(int bunnies)
    {
       if (bunnies == 0) return 0;
       else if (bunnies == 1) return 2;
       else return 2 + bunnyEars(bunnies - 1);
    }
    
  • 0
  • This method also stops for another value of n.
  • 1
  • This method also stops for another value of n.
  • Both 0 and 1
  • This method stops calling itself when n is either 0 or 1.
Next Section - 12.3. Why use Recursion?