## 7.6. Recursive FunctionsA In Example 7-8, the recursive function ## 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 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 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. |