递归和分治算法实验原理

递归和分治算法是两种常用的问题解决策略，尤其在计算机科学中处理复杂结构和大规模数据集时非常有效。

**递归**是一种通过将大问题分解成规模更小、结构相似的子问题的方式来解决问题的方法。它通常包含三个关键要素：基本情况（可以直接求解的小问题），递归情况（将问题缩小并调用自身），以及合并结果（当所有子问题解决后将结果组合）。递归过程中，函数或过程会反复地调用自身，直到达到基础条件才停止。例如，计算阶乘就是一个经典的递归例子：

def factorial(n):
    if n == 0 or n == 1:  # 基本情况
        return 1
    else:
        return n * factorial(n - 1)  # 递归情况

**分治算法**则是将一个大问题划分为两个或更多的相同或相似的部分（称为“分治”），然后分别解决每个部分，最后将它们的结果合并（“合”），形成原问题的解决方案。它通常包括三个步骤：分割（Divide）、解决（Conquer）、合并（Combine）。比如归并排序就是分治思想的一个经典实例：

def merge_sort(arr):
    if len(arr) <= 1:  # 基本情况
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):  # 合并部分
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result.extend(left if left else right)
    return result