C# 递归算法实现方法 C#如何编写一个递归函数

递归函数必须有前置终止条件，否则会无限调用导致栈溢出；C#栈空间有限（约1MB），递归过深即崩溃；终止判断须置于函数开头，不可依赖后续计算。

递归函数必须有明确的终止条件

没有终止条件的递归会无限调用，最终导致 StackOverflowException。C# 对栈深度有限制（通常约 1MB 栈空间），哪怕逻辑看似简单，一旦递归层级过深就崩溃。

写递归前先问自己：什么情况下该停止？这个判断必须放在函数开头，且不依赖后续计算。

• 错误写法：if (n == 0) return 1; 放在最后，中间还做了 n * Factorial(n-1) —— 此时已发生一次调用，没防住越界
• 正确写法：先检查 n ，立刻返回，再处理递归分支
• 对用户输入要额外校验：if (n

阶乘是最典型的 C# 递归示例

它直观体现「问题分解为相同结构的子问题」：求 n! 就是 n × (n−1)!，而 (n−1)! 又可继续拆解。

public static long Factorial(int n)
{
    if (n < 0) throw new ArgumentException("n must be non-negative");
    if (n <= 1) return 1; // 终止条件
    return n * Factorial(n - 1); // 递归调用
}

注意：long 类型仅支持到 20! 左右；超过需用 BigInteger。另外，Factorial(10000) 会直接栈溢出——这不是算法错，是 C# 运行时限制。

避免重复计算：斐波那契递归的坑

直接写 Fib(n) = Fib(n-1) + Fib(n-2) 看似自然，但时间复杂度是 O(2^n)，因为大量子问题被反复计算。

Figma

Figma 是一款基于云端的 UI 设计工具，可以在线进行产品原型、设计、评审、交付等工作。

下载

• 调用 Fib(5) 时，Fib(3) 被算两次，Fib(2) 被算三次
• Fib(45) 在普通机器上就要等好几秒，Fib(50) 更久
• 这不是递归本身的问题，而是没做记忆化（memoization）

若坚持递归，应缓存结果：

private static readonly Dictionary _memo = new();
public static long Fib(int n)
{
    if (n < 0) throw new ArgumentException("n must be non-negative");
    if (n <= 1) return n;
    if (_memo.TryGetValue(n, out var value)) return value;
    value = Fib(n - 1) + Fib(n - 2);
    _memo[n] = value;
    return value;
}

递归替代方案：什么时候该用循环

所有递归都能转成迭代（用栈或队列模拟调用栈），尤其当问题天然线性（如遍历树的深度优先）、或数据量大、或需精确控制内存时，迭代更稳。

• 文件系统遍历：递归易因路径过深崩溃，Directory.GetFiles(path, "*", SearchOption.AllDirectories) 内部是迭代实现
• 解析嵌套 JSON 或 XML：用栈比递归更易中断、调试和限深
• 尾递归优化？C# 编译器不支持自动尾调用优化（Tail Call Optimization），即使写成尾递归形式（最后一个操作是调用自身），仍会压栈

真正需要递归的场景其实不多：语法树解析、回溯算法（如八皇后）、分治（归并排序的合并逻辑）——这些结构天然递归，硬改成迭代反而难读难维护。