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". |

- one or multiple
*base cases*in which the problem can be solved directly (without recursion); - 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

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 Recursion |