试将折半查找法改写为递归算法。

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

int binarySearch(int arr[], int target, int length) {
    int left = 0, right = length - 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 binarySearchRecursion(int arr[], int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursion(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursion(arr, target, left, mid - 1);
    }
}

我们可以看到，在递归算法中，我们首先判断了递归的终止条件，即左指针大于右指针时，返回 -1。然后计算中间位置，如果中间位置的值等于目标值，直接返回 mid。否则，我们根据中间位置的值和目标值的大小关系分别递归查找左半部分和右半部分。