猫史档案馆

### Python递归函数教程

递归函数是一种调用自身的函数。在解决某些问题时，如计算阶乘、遍历树形结构、分治算法等，递归方法能够提供更简洁、更直观的解决方案。但是，递归也需要谨慎使用，因为不恰当的递归可能会导致栈溢出错误。

#### 1. 递归函数的基本结构

递归函数通常包含两个关键部分：
- **基准情形（Base Case）**：这是递归的终止条件，即函数不再调用自身的情形。
- **递归步骤（Recursive Step）**：在这一步，函数会调用自身，但参数需要有所变化，以趋近基准情形。

#### 2. 示例：计算阶乘

阶乘是所有小于及等于该数的正整数的积，符号为n!。例如，5! = 5 × 4 × 3 × 2 × 1 = 120。

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

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

#### 3. 注意事项

- **确保有基准情形**：递归函数必须有一个或多个基准情形，否则将无限递归，最终导致栈溢出。
- **避免过深的递归**：虽然Python的递归深度限制可以通过`sys.setrecursionlimit()`调整，但过深的递归仍然可能导致性能问题或栈溢出。
- **尾递归优化**：尾递归是一种特殊形式的递归，其中递归调用是函数中的最后一步操作。Python标准实现（喵ython）不自动优化尾递归，但在一些其他语言或Python的某些特殊实现中，尾递归可以被优化以避免栈溢出。

#### 4. 示例：斐波那契数列

斐波那契数列是一个每一项都是前两项和的数列，且前两项都是1。

```python
def fibonacci(n):
# 基准情形
if n <= 1:
return n
# 递归步骤
else:
return fibonacci(n-1) + fibonacci(n-2)

# 测试
print(fibonacci(10)) # 输出: 55
```

**注意**：虽然这个斐波那契数列的实现很直观，但由于它进行了大量的重复计算（例如，`fibonacci(n)`会多次计算`fibonacci(n-1)`和`fibonacci(n-2)`），因此效率非常低。在实际应用中，通常会使用迭代方法或带有记忆功能的递归（例如，使用装饰器`functools.lru_cache`）来提高效率。

#### 5. 总结

递归是一种强大的编程技术，可以简化复杂问题的解决。然而，它也要求程序员仔细设计基准情形和递归步骤，以避免无限递归和性能问题。通过实践和理解递归的基本原理，你可以更有效地利用这种技术来解决各种问题。

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

# 测试
num = 5
print(f"{num}! = {factorial(num)}")

def fibonacci(n):
    if n <= 0:  # 基本情况
        return 0
    elif n == 1:  # 基本情况
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # 递归调用

# 测试
num = 6
print(f"Fibonacci number at position {num} is {fibonacci(num)}")

def sum_list(lst):
    if not lst:  # 基本情况，空列表的总和为 0
        return 0
    else:
        return lst[0] + sum_list(lst[1:])  # 递归调用

# 测试
numbers = [1, 2, 3, 4, 5]
print(f"Sum of {numbers} is {sum_list(numbers)}")

def reverse_string(s):
    if len(s) == 0:  # 基本情况，空字符串
        return s
    else:
        return s[-1] + reverse_string(s[:-1])  # 递归调用

# 测试
text = "hello"
print(f"Reversed string of '{text}' is '{reverse_string(text)}'")