Some problems, eg traversing a tree, are better solved recursively because the recursive solution is so clear (see Binary Tree Traversal). Binary search is really is better in the non-recursive form, but it is one of the more plausible algorithms to use as an illustration of recursion.
This recursive version checks to see if we're at the key (in which case it can return), otherwise it calls itself so solve a smaller problem, ie, either the upper or lower half of the array.
int rBinarySearch(int sortedArray[], int first, int last, int key) { // function: // Searches sortedArray[first]..sortedArray[last] for key. // returns: index of the matching element if it finds key, // otherwise -(index where it could be inserted)-1. // parameters: // sortedArray in array of sorted (ascending) values. // first, last in lower and upper subscript bounds // key in value to search for. // returns: // index of key, or -insertion_position -1 // if key is not in the array. if (first <= last) { int mid = (first + last) / 2; // compute mid point. if (key == sortedArray[mid]) return mid; // found it. else if (key < sortedArray[mid]) // Call ourself for the lower part of the array return rBinarySearch(sortedArray, first, mid-1, key); else // Call ourself for the upper part of the array return rBinarySearch(sortedArray, mid+1, last, key); } return -(first + 1); // failed to find key }