factorial

递归是一种在编程中常用的技术，它允许函数调用自身来解决问题。递归函数必须能够到达一个明确的出口，即递归的结束条件，否则会导致无限递归。确定递归出口通常涉及设置一个或多个条件，当这些条件满足时，递归停止。

以下是几个具体案例，以及对如何确定递归出口的分析：

1. 计算阶乘

def factorial(n):
    if n == 0:  # 递归出口
        return 1
    else:
        return n * factorial(n - 1)

分析：在这个例子中，递归出口是当n等于0时。因为0的阶乘定义为1，所以当n减少到0时，函数返回1，不再进行递归调用。

2. 二分查找

def binary_search(arr, low, high, target):
    if low > high:  # 递归出口
        return -1  # 表示目标值不在数组中
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, mid + 1, high, target)
    else:
        return binary_search(arr, low, mid - 1, target)

分析：递归出口是当low大于high时，这意味着搜索区间已经无效，目标值不在数组中。每次递归调用都会缩小搜索区间的上下界。

3. 斐波那契数列

def fibonacci(n):
    if n <= 1:  # 递归出口
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

分析：在这个经典的例子中，递归出口是当n小于或等于1时。斐波那契数列定义中，fibonacci(0)是0，fibonacci(1)是1，所以当n减少到0或1时，函数直接返回n，不再进行递归调用。

4. 深度优先搜索（DFS）

def dfs(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)  # 标记顶点已访问
    for neighbour in graph[vertex]:
        if neighbour not in visited:
            dfs(graph, neighbour, visited)  # 递归调用
    return visited

分析：递归出口在这个例子中不是通过一个简单的条件判断，而是通过visited集合来确保不会重复访问同一个顶点。每次递归调用都会访问图中的一个未被访问过的顶点，直到所有顶点都被访问过。

5. 合并排序

def merge_sort(arr):
    if len(arr) <= 1:  # 递归出口
        return arr
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])  # 递归对左半部分排序
    right_half = merge_sort(arr[mid:])  # 递归对右半部分排序
    return merge(left_half, right_half)  # 合并排序好的两个半部分

分析：递归出口是当数组的大小小于或等于1时，这意味着数组已经是有序的，不需要进一步排序。

在所有的递归函数中，递归出口的设置对于避免无限递归和确保程序的正确性至关重要。递归出口通常基于问题的数学或逻辑性质来确定，并且递归函数的设计应该确保每次递归调用都更接近出口条件。