AP Computer Science A Unit 10: Recursion

What is the output of the following code?

public static String reverse(String s) {
    if (s.length() == 0) return "";
    return reverse(s.substring(1)) + s.charAt(0);
}
System.out.println(reverse("abc"));

A programmer wants to use recursion to check if a string is a palindrome. Which recursive definition is correct?

public static boolean isPalin(String s) {
    if (s.length() <= 1) return true;
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalin(s.substring(1, s.length() - 1));
}

What does isPalin("racecar") return?

What is the output of the following code?

public static void mystery(int n) {
    if (n <= 0) return;
    mystery(n - 1);
    System.out.println(n);
}
// Called with:
mystery(3);

Which of the following recursive methods contains a flaw that would cause infinite recursion for the call badRecurse(5)?

// Option A
public static int badRecurse(int n) {
    if (n == 0) return 0;
    return n + badRecurse(n + 1);
}

Consider the following recursive method:

public static int sumArray(int[] arr, int index) {
    if (index == arr.length) return 0;
    return arr[index] + sumArray(arr, index + 1);
}

What is returned by sumArray(new int[]{3, 1, 4, 1, 5}, 0)?

The Fibonacci sequence is defined as fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2) for n≥2. What does the following method return for fib(5)?

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

What value does the following method return when called with sum(4)?

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

What is the base case in the following recursive method?

public static int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

Consider the following method:

public static int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

How many times total is power called (including the initial call) when evaluating power(2, 4)?

What does the following method return when called with mystery(5)?

public static int mystery(int n) {
    if (n == 1) return 0;
    return 1 + mystery(n / 2);
}

What is the output of the following code?

public static void countdown(int n) {
    if (n == 0) {
        System.out.println("Go!");
        return;
    }
    System.out.println(n);
    countdown(n - 1);
}
// Called with:
countdown(3);

A recursive method and an iterative method both solve the same problem. Which of the following is a trade-off of choosing recursion over iteration?