Recursive vs. Iterative

Let’s compare the recursive binary search to the iterative version we had before.

Here is the iterative version, with the return type changed to boolean so the two versions can be compared more easily.

public static boolean binarySearch(int[] arr, int target) {
  int low = 0;
  int high = arr.length - 1;
  while (low <= high) {
    int mid = low + (high - low) / 2;
    int cmp = Integer.compare(arr[mid], target);
    if (cmp == 0) {
      return true;
    } else if (cmp < 0) {
      low = mid + 1;  // search the right half
    } else {
      high = mid - 1;  // search the left half
    }
  }
  return false;  // range is empty: the target is not present
}

And here is the recursive version:

public static boolean binarySearch(int[] arr, int target) {
  return binarySearch(arr, target, 0, arr.length - 1);
}

private static boolean binarySearch(int[] arr, int target, int low, int high) {
  if (low > high) {
    return false;  // range is empty: the target is not present
  }
  int mid = low + (high - low) / 2;
  int cmp = Integer.compare(arr[mid], target);
  if (cmp == 0) {
    return true;
  } else if (cmp < 0) {
    return binarySearch(arr, target, mid + 1, high);  // search the right half
  } else {
    return binarySearch(arr, target, low, mid - 1);  // search the left half
  }
}

Both versions do exactly the same comparisons in exactly the same order. The difference is how the narrowed range gets carried to the next step. The loop assigns it to low and high and goes around again. The recursion passes it as arguments to a new call.

But that does not make the two versions equivalent in performance.

When the iterative version is called, the program creates a single frame on the call stack for that call. A frame is a block of memory that stores the local variables and other information for a method call. For the iterative version, that frame contains arr, target, low, high, and mid. The loop reuses those variables for every step. When the loop finishes, the method returns and the frame is popped off the stack.

When the recursive version is called, the program creates a new frame on the call stack for the initial call, and then it creates a new frame for each recursive call. Each frame has its own copy of arr, target, low, high, and mid. (The array is a reference type, so the copies of arr are all references to the same array, but the other variables are primitive types, so each frame has its own copy.) Each frame stays on the stack until the call returns. So the more recursive calls there are, the more frames are on the stack, and the more memory is used.

So the recursive version ends up taking more memory than the iterative version. This is generally true of recursion. For binary search the number of steps it takes to find a target is small, so in practice this cost is negligible, but for other problems the number of steps can be large and the cost can be significant.

Recursion’s advantage is often that it is easier to write, and easier to read. Later in the course we will meet problems where the recursive version is much easier to write than the iterative version. For binary search, however, we generally prefer the iterative version.