1.3 Recursion1.2 Simple Sorting1 Algorithms and Data Structures in Java1.3.1 Printing a Number

1.3 Recursion

The algorithm for binary search solves the problem of finding an element in a sorted array within a specific index range. In each iteration, the algorithm reduces this problem to the problem of finding the element within an index range which is smaller than the original range. In other words, the problem is reduced to a simpler problem of the same kind.

We can express this formulation by the following Java methods:

  static int binarySearch(int[] a, int x)
  {
    return search(a, x, 0, a.length-1);
  }

  // ----------------------------------------------------------
  // i = search(a, x, low, high)
  // 'i' is the index of 'x' in 'a' in index range 'low...high'
  //
  // Input:
  //   'a' is not null and sorted in ascending order
  //   within 'low...high'
  // Output:
  //   'a' remains unchanged.
  //   if 'i == -1', then 'x' is not in 'a' within 'low...high'
  //   if 'i != -1', then 'low <= i <= high' and 'a[i] == x'
  // ----------------------------------------------------------
  static int search(int[] a, int x, int low, int high)
  {
    // x does not occur in a
    if (low > high) return -1;

    // x is found at mid
    int mid = (low + high)/2;
    if (a[mid] == x) return mid;

    // reduce problem to simpler problem
    if (x > a[mid])
      return search(a, x, mid+1, high);
    else
      return search(a, x, low, mid-1);
  }

Method binarySearch delegates the problem solution to a more general method search which takes the index range as its arguments. Method search first checks whether it can directly solve the problem, i.e., whether the search range is empty or the middle element equals the key. If the problem cannot be solved directly, it is reduced to a simpler problem of the same kind; search solves this problem by calling itself again.

This example demonstrates the programming technique of  recursion

"Recur" means "go back".
in which a method calls itself. A recursive method always has two parts:
  1. one or multiple  base cases in which the problem can be solved directly (without recursion);
  2. one or multiple  recursive cases in which the problem is reduced to simpler problems that are solved by recursive calls.

It is important that the base cases are always checked first and that in every recursive calls the problem is reduced to a simpler problem. Only then the base cases are eventually reached and the chain of recursive invocations terminates. Take for instance the array

Binary Search

in which we look for the value 11. This leads to the following chain of recursive invocations
  search(a, 11, 0, 7)    // mid == 3
   search(a, 11, 4, 7)   // mid == 5
     search(a, 11, 4, 4) // mid == 4
       return 4          // element found

This technique of reducing a problem to smaller problems of the same kind is also called  divide and conquer: the "divide" part is the reduction of the problem to simpler subproblem; the "conquer" part is the composition of the solution from the solutions of the subproblem. In above example, the composition part was trivial (the solution of the subproblem already represented the solution of the problem); we will see other examples where the composition is more demanding.


© Wolfgang Schreiner; February 3, 2005

1.3 Recursion1.2 Simple Sorting1 Algorithms and Data Structures in Java1.3.1 Printing a Number