Python递归调用如何返回值？以归并排序计数场景为例

当前代码的核心问题是mergeSort函数没有收集并返回递归过程中产生的逆序对总计数：子数组递归排序时的逆序对，加上合并阶段merge函数统计的逆序对，都没有被累计并向上传递。

解决步骤： #

• 修改mergeSort，让它返回累计的逆序对数量
• 单个元素（lo == hi）时，逆序对为0，直接返回0
• 递归处理左右子数组时，保存各自返回的逆序对计数
• 将左右子数组的计数与当前合并阶段merge返回的计数相加，作为当前函数的返回值

修改后的完整代码： #

def merge(arr, lo, hi):
    mid = (lo + hi) // 2
    c = 0
    i = lo
    j = mid + 1
    temp = []
    
    while i <= mid and j <= hi:
        if arr[i] > arr[j]:
            temp.append(arr[j])
            c += mid - i + 1
            j += 1
        else:
            temp.append(arr[i])
            i += 1
            
    temp.extend(arr[i:mid+1])
    temp.extend(arr[j:hi+1])
    
    for idx in range(len(temp)):
        arr[lo + idx] = temp[idx]
    return c

def mergeSort(arr, lo, hi):
    if lo == hi:
        return 0  # 单个元素无逆序对
    mid = (lo + hi) // 2
    # 收集左右子数组的逆序对计数
    left_count = mergeSort(arr, lo, mid)
    right_count = mergeSort(arr, mid + 1, hi)
    # 加上当前合并阶段的逆序对计数
    merge_count = merge(arr, lo, hi)
    # 返回累计总数
    return left_count + right_count + merge_count

调用示例： #

arr = [3, 1, 2, 4]
n = len(arr)
total_inversions = mergeSort(arr, 0, n-1)
print(total_inversions)  # 输出：2（对应(3,1)、(3,2)）

内容的提问来源于stack exchange，提问作者Dark Avenger