Recursion II: Helper Methods, Backtracking and Memoization

Why does a recursive palindrome check usually delegate to a private helper such as isPalindrome(String s, int lo, int hi)?

What does this call return?

static int count(int[] a, int i) {
    if (i == a.length) return 0;
    return (a[i] % 2 == 0 ? 1 : 0) + count(a, i + 1);
}

// ...
count(new int[]{3, 4, 6, 7, 8}, 2)

The recursive binary search below prints mid at every call. What is printed by search(a, 23, 0, 9)?

static int search(int[] a, int key, int low, int high) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    System.out.print(mid + " ");
    if (a[mid] == key) return mid;
    if (a[mid] < key) return search(a, key, mid + 1, high);
    return search(a, key, low, mid - 1);
}

int[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

Using the same search method and array as in the previous question, what does search(a, 60, 0, 9) print, and what does it return?

A student writes this binary search (note the first recursive call). With int[] a = {1, 3, 5};, which call ends with a StackOverflowError?

static int search(int[] a, int key, int low, int high) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (a[mid] == key) return mid;
    if (a[mid] < key) return search(a, key, mid, high);
    return search(a, key, low, mid - 1);
}

What is printed by show(3)?

static void show(int n) {
    if (n == 0) return;
    show(n - 1);
    System.out.print(n + " ");
    show(n - 1);
}

How many times is fib called in total (including the first call) when you evaluate fib(5)?

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

This memoized version counts its calls. What does calls hold after the first call mfib(6) (starting from calls == 0)?

static int calls = 0;
static long[] memo = new long[50];

static long mfib(int n) {
    calls++;
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = mfib(n - 1) + mfib(n - 2);
    return memo[n];
}

What is the time complexity of the naive recursive fib(n) (no memo)?

A student adds a HashMap memo to fib but writes the method like this. What happens when fib(20) is called?

static Map<Integer, Long> memo = new HashMap<>();

static long fib(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    long result = fib(n - 1) + fib(n - 2);
    return result;
}

Which recursive method would gain the most from memoization?

What does ways(5) return?

static int ways(int n) {           // steps of size 1, 2 or 3
    if (n < 0) return 0;
    if (n == 0) return 1;
    return ways(n - 1) + ways(n - 2) + ways(n - 3);
}

What is the fourth line printed by sub("abc", 0, "")?

static void sub(String s, int i, String cur) {
    if (i == s.length()) {
        System.out.println("[" + cur + "]");
        return;
    }
    sub(s, i + 1, cur + s.charAt(i));   // take s.charAt(i)
    sub(s, i + 1, cur);                 // leave it
}

For a string of length n (distinct characters), how many lines does the sub method of the previous question print?

What is the fourth word printed by perm("", "abc")?

static void perm(String done, String rest) {
    if (rest.isEmpty()) {
        System.out.print(done + " ");
        return;
    }
    for (int i = 0; i < rest.length(); i++)
        perm(done + rest.charAt(i),
             rest.substring(0, i) + rest.substring(i + 1));
}

How many lines does a permutation generator print for 5 distinct letters?

In this maze solver, why is the cell unmarked after the recursive calls?

static boolean solve(char[][] m, int r, int c) {
    if (r < 0 || c < 0 || r >= m.length || c >= m[0].length) return false;
    if (m[r][c] != '.') return false;          // wall or already on the path
    if (r == m.length - 1 && c == m[0].length - 1) return true;
    m[r][c] = '*';                              // choose
    if (solve(m, r + 1, c) || solve(m, r, c + 1)
            || solve(m, r - 1, c) || solve(m, r, c - 1)) return true;
    m[r][c] = '.';                              // un-choose
    return false;
}

The N-Queens solver in the concepts places exactly one queen in each row (col[row] = c). Which conflict check can therefore be left out of safe?

After running place(new int[4], 0) with the N-Queens code from the concepts, what is the value of solutions?

What is printed?

static String f(String s) {
    if (s.length() < 2) return s;
    return s.charAt(1) + s.charAt(0) + f(s.substring(2));
}

// ...
System.out.println(f("abcd"));

What happens when this program runs?

public class Deep {
    static int down(int n) {
        return down(n - 1) + 1;
    }

    public static void main(String[] args) {
        try {
            System.out.println(down(10));
        } catch (Exception e) {
            System.out.println("caught");
        }
        System.out.println("end");
    }
}

Does this method compile?

static int f(int n) {
    if (n <= 0) return 0;
    else if (n > 0) return n + f(n - 1);
}

How many calls (including the first) does slowPower(3, 16) make?

static long slowPower(long x, int n) {
    if (n == 0) return 1;
    if (n % 2 == 0) return slowPower(x, n / 2) * slowPower(x, n / 2);
    return x * slowPower(x, n / 2) * slowPower(x, n / 2);
}

Which statement about recursion and iteration in Java is true?

Explain why the naive recursive fib(n) makes an exponential number of calls, and how memoization reduces the running time. State the time and extra space of the memoized version.

A student implements recursive binary search by calling search(Arrays.copyOfRange(a, mid + 1, a.length), key) on the right half. Why is the version with low and high parameters better? Compare the cost of both.

Describe the three steps of the backtracking template (choose, explore, un-choose) using the problem "print all subsets of {3, 1, 4} whose sum is 4" as an example. What is pruning, and where would you prune here?

A recursive method sum(int[] a, int i) that returns a[i] + sum(a, i + 1) works for 1 000 elements but throws StackOverflowError for 1 000 000 elements. Explain why, and give two ways to fix it.

Write a public method static boolean isPalindrome(String s) that delegates to a private recursive helper with two index parameters. Do not call substring, reverse or any loop. isPalindrome("") and isPalindrome("a") must return true.

A robot starts in the top-left cell of an r × c grid and may only move right or down. Write static long gridPaths(int r, int c) that returns the number of different paths to the bottom-right cell, using recursion with a long[][] memo. gridPaths(1, 5) is 1, gridPaths(3, 3) is 6, and gridPaths(18, 18) must return quickly (2 333 606 220).