Recursive Traversals and Binary Search

A recursive traversal of a String

Recursion can traverse a String, an array, or an ArrayList. Each call works on a smaller part, and the base case is a part small enough to answer outright.

public static boolean mirror(String word)
{
    if (word.length() <= 1)
    {
        return true;
    }
    String first = word.substring(0, 1);
    String last = word.substring(word.length() - 1);
    if (!first.equals(last))
    {
        return false;
    }
    return mirror(word.substring(1, word.length() - 1));
}

The method checks whether a word reads the same backward. For "level", the outer letters match, so it calls itself on "eve", then on "v", which is short enough to return true. For "lever", the first call finds "l" and "r" different and returns false with no further call.

A recursive traversal of an array

An array has no substring. So instead of building a shorter copy, the recursive call passes a count of the elements still in play.

public static int maxOf(int[] nums, int count)
{
    if (count == 1)
    {
        return nums[0];
    }
    int rest = maxOf(nums, count - 1);
    if (nums[count - 1] > rest)
    {
        return nums[count - 1];
    }
    return rest;
}

For an array holding 14, 39, 8, and 27, the call maxOf(nums, 4) leads to calls with 3, 2, and 1. maxOf(nums, 1) returns 14. Each caller keeps the larger of that result and its own last element, so 39 comes back at every step and maxOf(nums, 4) returns 39. An ArrayList works the same way, with get(count - 1) in place of nums[count - 1].

Binary search

A sorted array of library card numbers:

int[] ids = {104, 117, 123, 135, 142, 156, 168, 171, 189};

A search keeps the indexes lo and hi of the part still in play, starting at 0 and 8. For 168, the middle index is 4, and 142 is less than 168. Since the array is sorted, 168 can't be at index 4 or below, so lo becomes 5. The new middle is (5 + 8) / 2, or 6, and ids[6] is 168. That's two elements examined, where a linear search from the front would examine seven.

For 160, which isn't there, the search examines 142, then 168, then 156. After that lo is 6 and hi is 5. Nothing is left in play, so the search returns -1.

Written recursively

Binary search can be written with a loop or recursively. In the recursive version, each call receives the bounds of the part still in play.

public static int seek(int[] ids, int target, int lo, int hi)
{
    if (lo > hi)
    {
        return -1;
    }
    int mid = (lo + hi) / 2;
    if (ids[mid] == target)
    {
        return mid;
    }
    if (ids[mid] < target)
    {
        return seek(ids, target, mid + 1, hi);
    }
    return seek(ids, target, lo, mid - 1);
}

Both new bounds skip mid itself, since that element has already been ruled out. The first call is seek(ids, target, 0, ids.length - 1). On a sorted array, binary search can be much more efficient than linear search, because each step removes about half of what's left. On unsorted data its comparisons say nothing about the half it discards, and its answer can be wrong.