chatgpt

递归算法的时间复杂度计算可以是复杂的，取决于递归的具体形式和问题的性质。一般来说，计算递归时间复杂度的常见方法是通过递归关系式（递归方程）和主定理（Master Theorem）。以下是一些常见的递归模式及其时间复杂度分析：

1. 线性递归

线性递归是指每次递归调用减少问题规模的递归。典型的例子是斐波那契数列和阶乘。

示例：

public int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

递归关系：T(n) = T(n-1) + O(1)

时间复杂度： O(n)

2. 二分递归

二分递归是指每次递归调用将问题规模减半。常见的例子是二分查找和归并排序。

示例：

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

递归关系：T(n) = T(n/2) + O(1)

时间复杂度： O(log n)

3. 多路递归

多路递归是指每次递归调用分成多个子问题。经典的例子是合并排序和快速排序。

示例（归并排序）：

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}