编辑“︁递归算法”︁

{{DISPLAYTITLE:递归算法}}  
'''递归算法'''是计算机科学中一种通过函数调用自身来解决问题的编程技巧。它将复杂问题分解为多个相同或相似的子问题，直到子问题可以直接求解为止。递归广泛应用于数学计算（如阶乘、斐波那契数列）、数据结构（如树、图的遍历）和算法设计（如分治、回溯）中。

== 基本概念 ==  
递归算法包含两个关键部分：  
# '''基线条件（Base Case）'''：递归终止的条件，防止无限调用。  
# '''递归条件（Recursive Case）'''：将问题分解为更小的子问题，并调用自身解决。  

递归的数学本质可通过递推关系表示。例如，阶乘的递归定义为：  
<math>n! = \begin{cases}  
1 & \text{if } n = 0 \quad (\text{基线条件}), \\  
n \times (n-1)! & \text{if } n > 0 \quad (\text{递归条件}).  
\end{cases}</math>

== 代码示例 ==  
=== 阶乘计算 ===  
以下是用Python实现的递归阶乘函数：  
<syntaxhighlight lang="python">  
def factorial(n):  
    if n == 0:  # 基线条件  
        return 1  
    else:       # 递归条件  
        return n * factorial(n - 1)  

# 示例输入输出  
print(factorial(5))  # 输出: 120  
</syntaxhighlight>  
**执行过程分析**：  
1. `factorial(5)` 调用 `5 * factorial(4)`  
2. `factorial(4)` 调用 `4 * factorial(3)`  
3. 此过程持续至 `factorial(0)` 返回1，逐层回溯计算结果。

=== 斐波那契数列 ===  
斐波那契数列的递归定义如下：  
<syntaxhighlight lang="python">  
def fibonacci(n):  
    if n <= 1:    # 基线条件  
        return n  
    else:         # 递归条件  
        return fibonacci(n - 1) + fibonacci(n - 2)  

print(fibonacci(6))  # 输出: 8 (序列: 0, 1, 1, 2, 3, 5, 8)  
</syntaxhighlight>  

== 递归与迭代对比 ==  
递归和迭代（循环）可解决同类问题，但各有优劣：  
{| class="wikitable"  
|+ 递归 vs 迭代  
! 特性 !! 递归 !! 迭代  
|-  
| 代码简洁性 || 高 || 低  
|-  
| 内存消耗 || 高（调用栈开销） || 低  
|-  
| 适用场景 || 问题自然递归（如树遍历） || 需优化效率时  
|}  

== 实际应用案例 ==  
=== 文件系统遍历 ===  
递归常用于遍历嵌套目录结构。以下示例列出目录下所有文件：  
<syntaxhighlight lang="python">  
import os  

def list_files(path):  
    for entry in os.listdir(path):  
        full_path = os.path.join(path, entry)  
        if os.path.isdir(full_path):  
            list_files(full_path)  # 递归调用  
        else:  
            print(full_path)  

list_files("/home/user/documents")  
</syntaxhighlight>  

=== 回溯算法 ===  
递归是回溯法（如八皇后问题）的核心。通过尝试可能的解并回溯，递归简化了状态管理。  

== 递归优化技术 ==  
=== 尾递归 ===  
若递归调用是函数的最后操作，可被编译器优化为循环（但Python未支持尾递归优化）：  
<syntaxhighlight lang="python">  
def tail_factorial(n, accumulator=1):  
    if n == 0:  
        return accumulator  
    return tail_factorial(n - 1, n * accumulator)  # 尾调用  
</syntaxhighlight>  

=== 记忆化（Memoization） ===  
缓存中间结果以避免重复计算，显著提升效率（如优化斐波那契数列）：  
<syntaxhighlight lang="python">  
from functools import lru_cache  

@lru_cache(maxsize=None)  
def memo_fibonacci(n):  
    if n <= 1:  
        return n  
    return memo_fibonacci(n - 1) + memo_fibonacci(n - 2)  
</syntaxhighlight>  

== 递归的可视化 ==  
以阶乘为例，递归调用栈的流程如下：  
<mermaid>  
graph TD  
    A["factorial(5)"] --> B["5 * factorial(4)"]  
    B --> C["4 * factorial(3)"]  
    C --> D["3 * factorial(2)"]  
    D --> E["2 * factorial(1)"]  
    E --> F["1 * factorial(0)"]  
    F --> G["返回1"]  
    G --> H["返回1"]  
    H --> I["返回2"]  
    I --> J["返回6"]  
    J --> K["返回24"]  
    K --> L["返回120"]  
</mermaid>  

== 常见问题与注意事项 ==  
* '''栈溢出'''：深层递归可能导致调用栈溢出，需设置合理的基线条件或改用迭代。  
* '''重复计算'''：如斐波那契数列的朴素递归存在指数级重复计算，需用记忆化优化。  
* '''调试技巧'''：使用打印语句或调试器观察递归调用栈。  

== 总结 ==  
递归通过分解问题简化代码逻辑，但需谨慎处理终止条件和性能。理解递归的核心在于把握“自相似性”和“分治思想”，并结合实际场景选择优化策略。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:算法基础]]