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

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

int binary_search(int arr[], int n, int target) {
    int left = 0, right = n - 1;

    while (left <= right) {
        int mid = (left + right) / 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) / 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 index = binary_search_recursive(arr, 0, n - 1, target);

递归算法的基本思路是将要查找的区间不断缩小，直到找到目标元素或者区间为空。在每一次递归中，都取中间位置的元素与目标元素进行比较，然后根据比较结果缩小查找区间。如果最终区间为空，说明没有找到目标元素，返回 -1。