# 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);
}
``````

### `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;
}
``````

### `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);
}
``````

### `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;
}
``````

### `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);
}
``````

### `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;
}
``````

### `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);
}
``````

### `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);
}
``````