Skip to main content
Logo image

BHSawesome2 AP CSA Java 2025+

Section 4.59 Recursion Exercises

Section 4.59.1 Recursion Base Case Practice

A recursive method contains a call to itself. The recursion stops when a base case test is true and a value is returned.
🔗

Activity 4.59.1.

🔗

Activity 4.59.2.

🔗

Activity 4.59.3.

🔗

Activity 4.59.4.

🔗
🔗

Section 4.59.2 Recursion Easier Multiple Choice Questions

These problems are easier than most of those that you will usually see on the AP CSA exam.
🔗

Activity 4.59.1.

Which line has the recursive call?
🔗
public static int factorial(int n)
{
    if (n == 0)
    {
        return 1;
    }
    else
    {
        return n * factorial(n-1);
    }
}
  • This is the method declaration. Look for a call to the same method in the body of the method.
  • This is a conditional, not a method call.
  • This is a return statement, not a method call.
  • This line contains a call to the same method which makes this method recursive.
🔗

Activity 4.59.2.

Which line has the recursive call?
🔗
public String starString(int n)
{
    if (n == 0)
    {
        return "*";
    }
    else
    {
        return starString(n - 1) + starString(n - 1);
    }
}
  • This is the method declaration. Look for a call to the same method in the body of the method.
  • This is a conditional, not a method call.
  • This is a return statement, not a method call.
  • This is an else which is part of a conditional, not a method call.
  • This line contains a call to the same method which makes this method recursive.
🔗

Activity 4.59.3.

How many recursive calls does the following method contain?
🔗
public static int fibonacci(int n)
{
    if (n == 0)
    {
        return 0;
    }
    else if (n == 1)
    {
        return 1;
    }
    else
    {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}
  • Look at line 13 more closely.
  • Many recursive methods only have one recursive call. But, this one has two.
  • Line 13 has two calls to fibonacci.
  • There are not 3 calls to fibonacci.
🔗

Activity 4.59.4.

How many recursive calls does the following method contain?
🔗
public static int multiplyEvens(int n)
{
    if (n == 1)
    {
        return 2;
    }
    else
    {
        return 2 * n * multiplyEvens(n - 1);
    }
}
  • Look for a call to the same method in the body of the method.
  • Line 9 has one call to multiplyEvens.
  • Where do you see 2 calls to multiplyEvens?
  • Where do you see 3 calls to multiplyEvens?
🔗
🔗

Section 4.59.3 Recursion Medium Multiple Choice Questions

These problems are similar to those you will see on the AP CSA exam.
🔗

Activity 4.59.1.

Given the following method declaration, which of the following is printed as the result of the call mystery(1234)?
🔗
//precondition:  x >=0
public static void mystery (int x)
{
    System.out.print(x % 10);

    if ((x / 10) != 0)
    {
        mystery(x / 10);
    }
    System.out.print(x % 10);
}
  • 1441
    🔗
  • The first call to mystery with the integer 1234 will print 1234 % 10. The ’%’ means remainder. The remainder of 1234 divided by 10 is 4 so the first thing printed must be 4.
  • 43211234
    🔗
  • This has a recursive call which means that the method calls itself when (x / 10) is greater than or equal to zero. Each time the method is called it prints the remainder of the passed value divided by 10 and then calls the method again with the result of the integer division of the passed number by 10 (which throws away the decimal part). After the recursion stops by (x / 10) == 0 the method will print the remainder of the passed value divided by 10 again.
  • 3443
    🔗
  • The first call to mystery with the integer 1234 will print 1234 % 10. The ’%’ means remainder. The remainder of 1234 divided by 10 is 4 so the first thing printed must be 4.
  • 12344321
    🔗
  • The first call to mystery with the integer 1234 will print 1234 % 10. The ’%’ means remainder. The remainder of 1234 divided by 10 is 4 so the first thing printed must be 4.
  • Many digits are printed due to infinite recursion.
    🔗
  • When the recursive call to mystery(1) occurs (the 4th call to mystery), the division of x /10 equals .01--this becomes 0 because this is integer division and the remainder is thrown away. Therefore the current call will be completed and all of the previous calls to mystery will be completed.
🔗
You can step through the code using the Java Visualizer by clicking on the following link: Q-11-7-1
 1 
http://cscircles.cemc.uwaterloo.ca/java_visualize/#code=public+class+ClassNameHere+%7B%0A+++%0A+++public+static+void+mystery+(int+x)%0A+++%7B%0A+++++++++System.out.print(x+%25+10)%3B%0A%0A+++++++++if+((x+/+10)+!%3D+0)%0A+++++++++%7B%0A++++++++++++mystery(x+/+10)%3B%0A+++++++++%7D%0A+++++++++System.out.print(x+%25+10)%3B%0A+++%7D%0A+++%0A+++public+static+void+main(String%5B%5D+args)+%7B%0A++++++mystery(1234)%3B%0A++++++%0A+++%7D%0A%7D&mode=display&curInstr=0
.
🔗

Activity 4.59.2.

Given the following method declaration, what value is returned as the result of the call mystery(5)?
🔗
public static int mystery(int n)
{
    if (n == 0)
    {
        return 1;
    }
    else
    {
        return 3 * mystery (n - 1);
    }
}
  • 243
    🔗
  • For the call mystery(5), n != 0 so the else statement is executed. This results in the next recursive call of mystery(4). This will continue until the call mystery(0) is executed. At this point, the value 1 will be returned. Then each call of mystery can return with the 3 * the result of the recursive call. So this method will compute 3 to the given power.
  • This can never be 0 because the stopping condition returns 1 when you call mystery(0)
  • This would only be true if you called mystery(1)
  • 81
    🔗
  • This would be true if you called mystery(4)
  • 27
    🔗
  • This would be true if you called mystery(3)
🔗
You can step through the code using the Java Visualizer by clicking on the following link: Q-11-7-2
 2 
http://cscircles.cemc.uwaterloo.ca/java_visualize/#code=public+class+ClassNameHere+%7B%0A+++%0A+++public+static+int+mystery(int+n)%0A+++%7B%0A+++++++++if+(n+%3D%3D+0)%0A++++++++++++return+1%3B%0A+++++++++else%0A++++++++++++return+3+*+mystery+(n+-+1)%3B%0A+++%7D%0A+++%0A+++public+static+void+main(String%5B%5D+args)+%7B%0A++++++System.out.println(mystery(5))%3B%0A++++++%0A+++%7D%0A%7D&mode=display&curInstr=0
.
🔗

Activity 4.59.3.

Given the following method declaration, what value is returned as the result of the call product(5)?
🔗
public static int product(int n)
{
   if (n <= 1)
   {
       return 1;
   }
   else
   {
       return n * product(n - 2);
   }
}
  • The value 1 will only be returned when the initial call to product is less than or equal to 1.
  • 10
    🔗
  • If you assume the purpose of the method is to compute n * 2, this is correct, but the product method does not do this. Be sure to trace the code to see what happens.
  • 25
    🔗
  • If you assume the purpose of the method is to compute n * n this is correct, but the product method does not do this. Be sure to trace the code to see what happens.
  • 3125
    🔗
  • If you assume the purpose of the method is to compute n ^ n, this would be correct. But product does not do this. Be sure to trace the code to see what happens.
  • 15
    🔗
  • The result from product(5) is 5 * product(3) which is 3 * product(1) which is 1 so the answer is 1 * 3 * 5 = 15.
🔗
You can step through the code using the Java Visualizer by clicking on the following link: Q11-7-3
 3 
http://cscircles.cemc.uwaterloo.ca/java_visualize/#code=public+class+ClassNameHere+%7B%0A+++%0A+++public+static+int+product(int+n)+%0A+++%7B%0A+++++++++if+(n+%3C%3D+1)%0A++++++++++++return+1%3B%0A+++++++++else%0A++++++++++++return+n+*+product(n+-+2)%3B%0A+++%7D%0A+++%0A+++public+static+void+main(String%5B%5D+args)+%7B%0A++++++System.out.println(product(5))%3B%0A++++++%0A+++%7D%0A%7D&mode=display&curInstr=0
.
🔗

Activity 4.59.4.

Given the following method declaration, what value is returned as the result of the call f(5)?
🔗
public static int f(int n)
{
   if (n == 0)
   {
       return 0;
   }
   else if (n == 1)
   {
       return 1;
   }
   else
   {
       return f(n-1) + f(n-2);
   }
}
  • This would be true if it was f(6) not f(5).
  • This would be true if it was f(4) not f(5).
  • There is no result because of infinite recursion.
    🔗
  • This method will stop when n equals 0 or 1.
  • This is the Fibonacci method which returns 0 for 0 and 1 for 1 and Fibonacci(n-1) + Fibonacci(n-2) for the rest of the numbers.
  • This would be true if it was f(0) not f(5).
🔗
You can step through the code using the Java Visualizer by clicking on the following link: Q11-7-4
 4 
http://cscircles.cemc.uwaterloo.ca/java_visualize/#code=public+class+ClassNameHere+%7B%0A+++%0A+++public+static+int+f(int+n)%0A+++%7B%0A+++++++++if+(n+%3D%3D+0)%0A++++++++++++return+0%3B%0A+++++++++else+if+(n+%3D%3D+1)%0A++++++++++++return+1%3B%0A+++++++++else+return+f(n-1)+%2B+f(n-2)%3B%0A+++%7D%0A+++%0A+++public+static+void+main(String%5B%5D+args)+%7B%0A++++++System.out.println(f(5))%3B%0A++++++%0A+++%7D%0A%7D&mode=display&curInstr=0
.
🔗
🔗

Section 4.59.4 Recursion Hard Multiple Choice Questions

These problems are about the same or harder than those that you will typically see on the AP CSA exam.
🔗

Activity 4.59.1.

Given the following method declaration, this method will return true if and only if:
🔗
public static boolean check(String s)
{
   return s.length() >= 2 &&
          (s.charAt(0) == s.charAt(1) ||
           check(s.substring(1)));
}
  • The string s contains two or more of the same characters.
    🔗
  • It is not enough for s to contain two of the same characters, they must be adjacent to satisfy s.charAt(0) == s.charAt(1).
  • The string s starts with two or more of the same characters.
    🔗
  • It is not neccessary for the adjacent characters to be at the start of the string.
  • The string s contains two or more of the same character that are next to each other.
    🔗
  • This method will return true when s has at least 2 characters in it and at least 2 characters are the same and are adjacent.
  • The string s ends with two or more of the same characters
    🔗
  • It is not neccessary for the adjacent characters to be at the end of the string.
🔗
You can step through the code above by clicking on the following link Ex-11-8-1
 1 
http://cscircles.cemc.uwaterloo.ca/java_visualize/#code=public+class+ClassNameHere+%7B%0A+++%0A+++public+static+boolean+check(String+s)%0A+++%7B%0A++++++return+s.length()+%3E%3D+2+%26%26%0A++++++++++(s.charAt(0)+%3D%3D+s.charAt(1)+%7C%7C%0A+++++++++++check(s.substring(1)))%3B%0A+++%7D%0A+++%0A+++public+static+void+main(String%5B%5D+args)+%7B%0A++++++System.out.println(check(%22xyyz%22))%3B%0A++++++System.out.println(check(%22xyxyz%22))%3B%0A++++++System.out.println(check(%22zyxzyy%22))%3B%0A++++++%0A+++%7D%0A%7D&mode=display&curInstr=0
.
🔗

Activity 4.59.2.

Given the following method declaration, what will redo(82, 3) return?
🔗
public static int redo(int i, int j)
{
    if (i == 0)
    {
        return 0;
    }
    else
    {
        return redo(i / j, j) + 1;
    }
}
  • The first time the method is called, i is not equal to 0, so the method makes a recursive call to itself, with the value of 82/3 which equals 27 due to integer division. This is still not equal to 0, so the method calls itself with the first parameter equal to 9, then 3, then 1. Finally, the method is called with the first parameter of 1/3 which equals 0 due to integer division which throws away any decimal part. Each method call adds 1 to the result, except for the final call when i is equal to 0.
  • Each time the method is called when i is not equal to 0, the return value is incremented. This happens 5 times, with i equal to 81, 27, 9, 3, and 1.
  • The return value is not incremented the last time the method is called, when i is equal to 0.
  • The method only executes 6 times, with the return value incremented each time i is not equal to zero
  • The method never returns due to infinite recursion.
    🔗
  • Infinite recursion would happen if the method never reached its base case where i is equal to 0. This would be true if the division could result in a constantly shrinking fraction, but integer division truncates the fractional portion of the division.
🔗
You can step through the code above by clicking on the following link Ex-11-8-2
 2 
http://cscircles.cemc.uwaterloo.ca/java_visualize/#code=public+class+ClassNameHere+%7B%0A+++%0A+++public+static+int+redo(int+i,+int+j)%0A+++%7B%0A++++++if+(i%3D%3D0)%0A+++++++++return+0%3B%0A++++++else+%0A+++++++++return+redo(i/j,+j)%2B1%3B%0A+++%7D%0A+++%0A+++public+static+void+main(String%5B%5D+args)+%7B%0A++++++System.out.println(redo(82,3))%3B%0A+++%7D%0A%7D&mode=display&curInstr=0
.
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext