Analyzing recursive methods

Recursion problems on the AP CS A Exam can be approached by analysis or by tracing. As with non-recursive problems, analysis is the preferred technique vs tracing. As with non-recursive problems, we only consider tracing if the input is provided. In all cases, we favor analysis.

My Recursive method tracing technique demonstrates the alternative approach.

Recursive methods with print statements can sometimes be handled specially. See Recursive methods with print statements.

Recursive method analysis technique

When analyzing recursive methods, consider the aspects below.

Base case(s)

Does the method have a base case or base cases? A method on an exam question might be missing a base case. Recognizing that a method is missing a base case is crucial.

What does the method do when the base case(s) is (are) reached? Some base cases provide few hints but eliminate certain possibilities. Other base cases suggest what the method does.

Recursive call(s)

With what value(s) does the method call itself? Trying to figure out what a recursive call does is a common mistake. If we knew what the call did, we wouldn’t be analyzing the method. Instead, consider what is being passed as arguments.

Does each recursive call get closer to the base case(s)? Would repeatedly doing what each call does eventually hit the base case(s)? A method on an exam question may make a call that gets farther from the base case(s) or a sequence of calls that skips the base case(s).

Work on 1 step

What does the method do during a single execution? Trying to step into the recursive call(s) is a common mistake. Focus on what the method does during a single execution. What does it do with the value(s) of the parameter(s)? What else is done during the method?

Recursive method analysis practice

A link to the solutions is at the bottom of this section.

Each method does something coherent. Describe what each method does.

mystery1 method

public static int mystery1(int n)
{
    if(n == 0)
        return 0;
    
    if(n % 2 == 1)
        return 1 + mystery1(n / 10);
    else
        return mystery1(n / 10);
}

mystery1 solution

mystery2 method

public static int mystery2(int n)
{
    if(n == 0)
        return 0;
    
    int c = mystery2(n / 10);
    
    if(n % 2 == 1)
        c++;
    
    return c;
}

mystery2 solution

mystery3 method

public static int mystery3(int n)
{
    if(n == 0)
        return 0;
    
    if(n % 2 == 0)
        return n % 10 + mystery3(n / 10);
    else
        return mystery3(n / 10);
}

mystery3 solution

mystery4 method

public static int mystery4(String str, String p)
{
    if(str.length() < p.length())
        return 0;
    
    int c = mystery4(str.substring(1), p);
    
    if(str.substring(0, p.length()).equals(p))
        c++;
    
    return c;
}

mystery4 solution

mystery5 method

public static String mystery5(String str, String fnd, String rpl)
{
    if(str.length() < fnd.length())
        return str;
    
    if(str.substring(0, fnd.length()).equals(fnd))
        return rpl + mystery5(str.substring(fnd.length()), fnd, rpl);
    else
        return str.substring(0, 1) + mystery5(str.substring(1), fnd, rpl);
}

mystery5 solution

mystery6 methods

The public method calls the private recursive helper method.

public static int mystery6(int[] arr)
{
    return mystery6(arr, 0);
}

private static int mystery6(int[] arr, int index)
{
    if(index >= arr.length)
        return 0;
    
    int c = mystery6(arr, index + 1);
    
    if(arr[index] < 0)
        c++;
    
    return c;
}

mystery6 solution

mystery7 methods

public static void mystery7(int[] arr, int a, int b)
{
    mystery7(arr, a, b, 0);
}

private static void mystery7(int[] arr, int a, int b, int index)
{
    if(index >= arr.length)
        return;
    
    if(arr[index] < a)
        arr[index] = a;
    
    if(arr[index] > b)
        arr[index] = b;
    
    mystery7(arr, a, b, index + 1);
}

mystery7 solution

mystery8 methods

public static int[] mystery8(int[] arr)
{
    int[] newArr = new int[arr.length * 2];
    mystery8(arr, newArr, 0);
    return newArr;
}

private static void mystery8(int[] oldArr, int[] newArr, int oldIndex)
{
    if(oldIndex >= oldArr.length)
        return;
    
    newArr[oldIndex] = oldArr[oldIndex];
    newArr[oldArr.length + oldIndex] = oldArr[oldIndex];
    
    mystery8(oldArr, newArr, oldIndex + 1);
}

mystery8 solution

Solutions & comments

See the Recursive method analysis solutions or review them with AP CS Tutor Brandon Horn.

Comment on Analyzing recursive methods

More recursion resources