编辑“︁C Sharp 递归”︁

= C#递归 =

== 介绍 ==
'''递归'''是编程中一种强大的技术，指函数直接或间接调用自身的过程。在C#中，递归常用于解决可分解为相似子问题的问题（如数学中的阶乘、斐波那契数列，或文件系统的遍历）。递归的核心思想是：
* '''基准条件（Base Case）'''：终止递归的条件。
* '''递归条件（Recursive Case）'''：函数调用自身的逻辑。

== 基本语法 ==
递归函数的通用结构如下：
<syntaxhighlight lang="csharp">
ReturnType RecursiveFunction(parameters)
{
    // 1. 基准条件
    if (baseCaseCondition)
        return baseCaseValue;

    // 2. 递归条件
    return RecursiveFunction(modifiedParameters);
}
</syntaxhighlight>

== 示例：计算阶乘 ==
阶乘（n!）是经典的递归案例。数学定义为：
<math>n! = n \times (n-1)! \quad \text{且} \quad 0! = 1</math>

<syntaxhighlight lang="csharp">
int Factorial(int n)
{
    // 基准条件
    if (n == 0)
        return 1;
    
    // 递归条件
    return n * Factorial(n - 1);
}

// 调用示例
Console.WriteLine(Factorial(5)); // 输出: 120
</syntaxhighlight>

'''执行流程'''（以n=3为例）：
<mermaid>
graph TD
    A[Factorial(3)] --> B[3 * Factorial(2)]
    B --> C[2 * Factorial(1)]
    C --> D[1 * Factorial(0)]
    D --> E[返回1]
    E --> F[返回1*1=1]
    F --> G[返回2*1=2]
    G --> H[返回3*2=6]
</mermaid>

== 示例：斐波那契数列 ==
斐波那契数列定义为：
<math>F(n) = F(n-1) + F(n-2) \quad \text{且} \quad F(0)=0, F(1)=1</math>

<syntaxhighlight lang="csharp">
int Fibonacci(int n)
{
    // 基准条件
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    // 递归条件
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

// 调用示例
Console.WriteLine(Fibonacci(6)); // 输出: 8
</syntaxhighlight>

== 递归与迭代对比 ==
{| class="wikitable"
|-
! 特性 !! 递归 !! 迭代
|-
| 代码简洁性 || 高 || 低
|-
| 内存消耗 || 高（调用栈累积） || 低
|-
| 适用场景 || 问题自然递归（如树遍历） || 线性问题（如简单循环）
|}

== 实际应用：目录遍历 ==
递归适合处理嵌套结构，例如遍历文件夹：
<syntaxhighlight lang="csharp">
void TraverseDirectory(string path)
{
    foreach (var file in Directory.GetFiles(path))
        Console.WriteLine($"文件: {file}");

    foreach (var dir in Directory.GetDirectories(path))
    {
        Console.WriteLine($"进入目录: {dir}");
        TraverseDirectory(dir); // 递归调用
    }
}

// 调用示例
TraverseDirectory(@"C:\MyProject");
</syntaxhighlight>

== 尾递归优化 ==
C#编译器不自动优化尾递归，但可通过改写避免栈溢出：
<syntaxhighlight lang="csharp">
int FactorialTailRec(int n, int accumulator = 1)
{
    if (n == 0) return accumulator;
    return FactorialTailRec(n - 1, n * accumulator); // 尾调用
}
</syntaxhighlight>

== 常见错误与调试 ==
* '''栈溢出'''：未正确定义基准条件。
* '''性能问题'''：重复计算（如斐波那契的朴素递归解法效率为O(2^n)）。
* 调试技巧：使用<code>System.Diagnostics.Debug.WriteLine</code>打印调用层次。

== 进阶主题 ==
* '''记忆化（Memoization）'''：缓存计算结果提升效率。
* '''间接递归'''：函数A调用函数B，B再调用A。
* '''递归与LINQ'''：结合<code>yield return</code>实现惰性求值。

== 总结 ==
递归是C#中解决分治问题的有力工具，但需谨慎处理终止条件和性能。对于初学者，建议从数学示例开始，逐步过渡到实际场景如树形数据处理。

[[Category:编程语言]]
[[Category:C Sharp]]
[[Category:C Sharp 函数]]