将折半查找算法改写成递归算法

折半查找算法的非递归实现如下：

int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

下面是折半查找算法的递归实现：

int binary_search_recursive(int arr[], int left, int right, int target) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binary_search_recursive(arr, mid + 1, right, target);
    } else {
        return binary_search_recursive(arr, left, mid - 1, target);
    }
}

int binary_search(int arr[], int n, int target) {
    return binary_search_recursive(arr, 0, n - 1, target);
}

在递归实现中，我们将查找范围的左边界和右边界作为参数传入递归函数中，每次递归都将查找范围缩小一半，直到找到目标元素或者查找范围为空。