Recursion FRQ Practice

Responses receive AI feedback against a rubric after submission. Scores are practice estimates.

Question 1 of 5

A tile pattern uses power(2, 5).

public static int power(int base, int exp)
{
    if (exp == 0)
    {
        return 1;
    }
    return base * power(base, exp - 1);
}
Call base exp Value returned
1 (original) 2 5
2 2 4
3 2 3
4 2 2
5 2 1
6 2 0

(a) Fill the returned values from the base case upward. (b) State how many calls occur, including the original. (c) Identify the base case.

Question 2 of 5

Trace fib(4). Each call has its own n.

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

(a) Draw or list the call tree for fib(4), including repeated calls. (b) State the value returned by fib(4). (c) State how many times fib is called in total, including the original call.

Question 3 of 5

Trace reverse on the kite tag "kite".

public static String reverse(String s)
{
    if (s.length() <= 1)
    {
        return s;
    }
    return reverse(s.substring(1)) + s.substring(0, 1);
}

(a) List each call's argument in the order the calls begin. (b) For each call, state the substring(1) argument sent onward and the substring(0, 1) piece that is concatenated after the recursive return. (c) State the final return value. Do not write a different recursive method.

Question 4 of 5

A booth method stores a local copy of n in step.

public static int fold(int n)
{
    int step = n;
    if (n <= 0)
    {
        return step;
    }
    return step + fold(n - 1);
}

(a) State the value of fold(3). (b) For the original call and for fold(1), state the local step in each call. (c) Explain why changing step in fold(1) does not change step in fold(3).

Question 5 of 5

A clerk traces countA("BA") and then describes an equivalent loop in words.

public static int countA(String s)
{
    if (s.length() == 0)
    {
        return 0;
    }
    int add = 0;
    if (s.substring(0, 1).equals("A"))
    {
        add = 1;
    }
    return add + countA(s.substring(1));
}

(a) List each call's s value and the add in that call. (b) State the return value of countA("BA") and the total number of calls, including the original. (c) In words, describe an equivalent iterative process that counts A characters. Identify the base case of the given method. Do not write a recursive method.