递归函数是一种在函数内部调用自身的编程技术

递归函数是一种在函数内部调用自身的编程技术。递归函数通常用于解决具有重复子问题的问题，例如计算阶乘、斐波那契数列和遍历树结构等。

1. 基本概念

递归函数有两个主要部分：

• 基准情况（Base Case）：这是递归终止的条件。当满足基准情况时，递归不再继续，直接返回结果。
• 递归步骤（Recursive Step）：这是函数调用自身的地方，每次调用都会使问题规模缩小，逐步接近基准情况。

2. 示例：计算阶乘

阶乘是一个经典的递归问题。n的阶乘（记作n!）定义为：

• n! = n * (n-1)!
• 0! = 1

实现代码

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

# 测试
print(factorial(5))  # 输出 120

在这个例子中，factorial 函数首先检查 n 是否为 0。如果是，则返回 1（基准情况）。否则，它返回 n 乘以 factorial(n - 1)，即递归调用自身。

3. 示例：计算斐波那契数列

斐波那契数列是另一个常见的递归问题。斐波那契数列的定义如下：

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) for n > 1

实现代码

def fibonacci(n):
    # 基准情况
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # 递归步骤
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 测试
print(fibonacci(6))  # 输出 8

在这个例子中，fibonacci 函数首先检查 n 是否为 0 或 1。如果是，则返回相应的值（基准情况）。否则，它返回 fibonacci(n - 1) 和 fibonacci(n - 2) 的和，即递归调用自身。

4. 示例：遍历二叉树

递归也常用于数据结构的遍历，例如二叉树。假设我们有一个简单的二叉树节点类：

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

我们可以使用递归来遍历二叉树：

实现代码

def inorder_traversal(node):
    if node is not None:
        inorder_traversal(node.left)  # 递归遍历左子树
        print(node.value)             # 访问当前节点
        inorder_traversal(node.right) # 递归遍历右子树

# 创建一个简单的二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 测试
inorder_traversal(root)  # 输出 4 2 5 1 3

在这个例子中，inorder_traversal 函数首先检查当前节点是否为空。如果不为空，则递归遍历左子树，访问当前节点，然后递归遍历右子树。

5. 注意事项

• 基准情况：确保每个递归函数都有一个明确的基准情况，以防止无限递归。
• 性能问题：递归可能导致大量的函数调用，特别是在没有优化的情况下（如斐波那契数列的简单递归实现）。可以使用记忆化（Memoization）或动态规划来优化性能。
• 栈溢出：Python 默认的递归深度限制为 1000，可以通过 sys.setrecursionlimit() 修改这个限制，但应谨慎使用，以避免栈溢出错误。

通过这些示例和注意事项，你可以在 Python 中有效地实现和使用递归函数。