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

好的，我来为您解答。折半查找法也叫二分查找法，是一种很常用的查找算法。下面是折半查找法的非递归实现：

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

现在我们将其改写为递归算法：

int binarySearchRecursion(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 binarySearchRecursion(arr, left, mid - 1, target);
    else
        return binarySearchRecursion(arr, mid + 1, right, target);
}

可以看到，递归算法的思想与非递归算法相同，只是将循环改成了递归函数调用，同时将循环条件改为递归终止条件。