As a simple rule of recursion, any function can be computed using a recursive routine if :
1. The function can be expressed in its own form.
2. There exists a termination step, the point at which f(x) is known for a particular ‘x’.

Therefore to write a recursive program for the binary search, we have to express the binary search function in a recursive form using the above 2 rules :

where ‘n’ is the element to be searched and low and high the lower and upper bounds of the array

2.  if(n == a[mid]) print mid.      (termination step)

The exe file can be downloaded from here : Recursive Binary Search

Using these 2 rules, the recursive program for binary search can be coded very easily as shown :

#include "stdio.h"
binarysearch(int a[],int n,int low,int high)
	{ int mid;
	  if (low > high)
	   return -1;
	  mid = (low + high)/2;
	  if(n == a[mid])
	    { printf("The element is at position %d\n",mid+1);
	      return 0;
	    }
	  if(n < a[mid])
	    { high = mid - 1;
	      binarysearch(a,n,low,high);
	    }
	  if(n > a[mid])
	    { low = mid + 1;
	      binarysearch(a,n,low,high);
	    }
	 }

main()
	{ int a[50];
	  int n,no,x,result;
	  printf("Enter the number of terms : ");
	  scanf("%d",&no);
	  printf("Enter the elements :\n");
	  for(x=0;x&ltno;x++)
	   scanf("%d",&a[x]);
	  printf("Enter the number to be searched : ");
	  scanf("%d",&n);
	  result = binarysearch(a,n,0,no-1);
	  if(result == -1)
	   printf("Element not found");
	  return 0;
	}