7.6. Recursive Functions

A recursive function is one that calls itself, whether directly or indirectly. Indirect recursion means that a function calls another function (which may call a third function, and so on), which in turn calls the first function. Because a function cannot continue calling itself endlessly, recursive functions must always have an exit condition.

In Example 7-8, the recursive function binarySearch( ) implements the binary search algorithm to find a specified element in a sorted array. First the function compares the search criterion with the middle element in the array. If they are the same, the function returns a pointer to the element found. If not, the function searches in whichever half of the array could contain the specified element by calling itself recursively. If the length of the array that remains to be searched reaches zero, then the specified element is not present, and the recursion is aborted.

Example 7-8. Function binarySearch( )

// The binarySearch( ) function searches a sorted array.
// Arguments:    The value of the element to find;
//               the array of long to search; the array length.
// Return value: A pointer to the element found,
//               or NULL if the element is not present in the array.

long *binarySearch( long val, long array[ ], int n )
{
  int m = n/2;
  if ( n <= 0 )          return NULL;
  if ( val == array[m] ) return array + m;
  if ( val <  array[m] ) return binarySearch( val, array, m );
  else                   return binarySearch( val, array+m+1, n-m-1 );
}

For an array of n elements, the binary search algorithm performs at most 1+log₂(n) comparisons. With a million elements, the maximum number of comparisons performed is 20, which means at most 20 recursions of the binarySearch( ) function.

Recursive functions depend on the fact that a function's automatic variables are created anew on each recursive call. These variables, and the caller's address for the return jump, are stored on the stack with each recursion of the function that begins. It is up to the programmer to make sure that there is enough space available on the stack. The binarySearch( ) function as defined in Example 7-8 does not place excessive demands on the stack size, though.

Recursive functions are a logical way to implement algorithms that are by nature recursive, such as the binary search technique, or navigation in tree structures. However, even when recursive functions offer an elegant and compact solution to a problem, simple solutions using loops are often possible as well. For example, you could rewrite the binary search in Example 7-8 with a loop statement instead of a recursive function call. In such cases, the iterative solution is generally faster in execution than the recursive function.