Переделать под реккурсию

#include <iostream>
#include <conio.h>
using namespace std;
 
int BinSearch(int *M, int n, int k);    //(int *M, int n, int k)-÷òî çàä.â êà÷åñòâå ïàðàìåòðîâ?!
 
int main()
{
    const int n=9;                 // ÷òî îáîçíà÷àåò?
    int A[n];
    int x,j,a,i;
 
    for (size_t i=0; i<n; i++)
    {
        cout << "Vvedite A[" << i << "] = ";
        cin >> A[i];
    }
        for (size_t i=0; i<n; i++)
    {
printf("%i ",A[i]);
    }
    puts("");
 
    for(j=1; j<n; j++)
    for (i=0; i<n-j; i++)
    {
        if (A[i]>A[i+1])
        {
            a=A[i];
            A[i]=A[i+1];
            A[i+1]=a;
        }
    }
 puts("");
 puts("Otsortirovaniy masiv: ");
puts("");
for (i=0; i<n; i++){
printf("%i ",A[i]);
 
}
           puts("");
    cout << "Nayti Eto 4islo -> ";
    cin >> x;
 
       puts("4islo pod indexom: ");
    cout << BinSearch(A, n, x);
    getch();
    return 0;
}
 
int BinSearch(int *M, int n, int k)
{
    int L = 0;
    int R = n;
    int m;
    int z = 0;
 
    while (L<R)    {
        z++;
        m = (L+R)/2;
if (k > M[m]) L = m;
        if (k < M[m]) R = m;
        if (k == M[m]) return m;
    }
    return -1;
        }