Python 中 15 个递归函数经典实例剖析

在 Python 编程中，递归函数是一种强大而富有挑战性的概念。它通过在函数内部调用自身来解决问题，能够简洁地处理一些复杂的逻辑。以下为您详细剖析 15 个经典的递归函数实例。

实例 1：计算阶乘

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

实例 2：斐波那契数列

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

实例 3：计算列表元素之和

def list_sum(lst):
    if not lst:
        return 0
    else:
        return lst[0] + list_sum(lst[1:])

实例 4：反转字符串

def reverse_string(s):
    if len(s) == 0:
        return s
    else:
        return reverse_string(s[1:]) + s[0]

实例 5：计算二叉树节点个数

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_nodes(root):
    if root is None:
        return 0
    else:
        return 1 + count_nodes(root.left) + count_nodes(root.right)

实例 6：求最大公约数

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

实例 7：汉诺塔问题

def hanoi(n, src, aux, dest):
    if n == 1:
        print(f"Move disk 1 from {src} to {dest}")
        return
    hanoi(n - 1, src, dest, aux)
    print(f"Move disk {n} from {src} to {dest}")
    hanoi(n - 1, aux, src, dest)

实例 8：生成全排列

def permute(lst):
    if len(lst) == 0:
        return []
    if len(lst) == 1:
        return [lst]
    result = []
    for i in range(len(lst)):
        m = lst[i]
        rem_lst = lst[:i] + lst[i + 1:]
        for p in permute(rem_lst):
            result.append([m] + p)
    return result

实例 9：判断回文

def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0]!= s[-1]:
        return False
    return is_palindrome(s[1:-1])

实例 10：数字转换为字符串

def num_to_str(n):
    if n < 10:
        return str(n)
    else:
        return num_to_str(n // 10) + str(n % 10)

实例 11：求数组最大值

def max_in_list(lst):
    if len(lst) == 1:
        return lst[0]
    else:
        return max(lst[0], max_in_list(lst[1:]))

实例 12：计算指数

def power(base, exp):
    if exp == 0:
        return 1
    else:
        return base * power(base, exp - 1)

实例 13：生成杨辉三角

def pascal_triangle(n):
    if n == 0:
        return [1]
    else:
        prev_row = pascal_triangle(n - 1)
        new_row = [1]
        for i in range(len(prev_row) - 1):
            new_row.append(prev_row[i] + prev_row[i + 1])
        new_row.append(1)
        return new_row

实例 14：合并排序

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    mid = len(lst) // 2
    left_half = merge_sort(lst[:mid])
    right_half = merge_sort(lst[mid:])
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

实例 15：快速排序

def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    pivot = lst[len(lst) // 2]
    less = [x for x in lst if x < pivot]
    greater = [x for x in lst if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

通过对这 15 个经典递归函数实例的剖析，相信您对 Python 中的递归函数有了更深入的理解和掌握。在实际编程中，合理运用递归函数可以使代码更加简洁高效，但也要注意递归的深度和性能问题，避免出现栈溢出等错误。