第八章 递归与尾递归

递归分类

• 普通递归: 递归调用·不是· 函数的最后一步
• 尾递归: 递归调用 ·是· 函数的最后一步

‍

尾递归可以被编译器优化,以提高性能,防止栈溢出.

递归应该尽量尾递归

缓解堆栈溢出风险的策略

• 尾递归
• 别递了
• 增加堆栈大小：通过设置 System.Threading.Thread.MaxStackSize 属性
• 限制递归深度：递归实现时追踪递归深度,太深了直接抛异常

‍

C#递归代码优雅手段

局部函数

void ProcessAndCountVideosInCategory(Category category)
{
    int videoCount = 0;

    // 局部函数：递归统计视频数量
    void CountVideos(Category cat)
    {
        foreach (var subcategory in cat.Subcategories)
        {
            CountVideos(subcategory); // 递归调用
        }
        videoCount += cat.Videos.Count;
    }

    CountVideos(category); // 从顶层分类开始递归
    Console.WriteLine($"总视频数：{videoCount}");
}

模式匹配

void ProcessVideoCategory(Category category)
{
    switch (category)
    {
        case Category c when c.HasSubcategories:
            foreach (var subcategory in c.Subcategories)
            {
                ProcessVideoCategory(subcategory); // 递归调用
            }
            break;

        // 可以添加更多 case 来处理其他类型或条件
    }
}

‍

高级递归模式

互递归（Mutual Recursion）

两个或多个函数相互调用

public void EditContent(Manuscript manuscript)
    {
        Console.WriteLine($"正在编辑内容：{manuscript.Title}");
        manuscript.ContentEdited = true;
        manuscript.ContentIssues.Clear(); // 假设内容问题已解决

        // 模拟发现格式问题
        manuscript.FormatIssues.Add("章节标题不一致");

        if (manuscript.FormatIssues.Any())
        {
            EditFormat(manuscript); // 调用格式编辑
        }
    }

    public void EditFormat(Manuscript manuscript)
    {
        Console.WriteLine($"正在调整格式：{manuscript.Title}");
        manuscript.FormatEdited = true;
        manuscript.FormatIssues.Clear(); // 假设格式问题已解决

        // 模拟发现内容问题
        manuscript.ContentIssues.Add("第三章内容过长");

        if (manuscript.ContentIssues.Any())
        {
            EditContent(manuscript); // 调用内容编辑
        }
    }

记忆化（Memoization）

空间换时间

public class FibonacciCalculator
{
    private Dictionary<int, long> memo = new();

    public long Calculate(int n)
    {
        if (n == 0) return 0;
        if (n == 1) return 1;

        if (memo.ContainsKey(n))
        {
            return memo[n]; // 从缓存中返回结果
        }

        long result = Calculate(n - 1) + Calculate(n - 2);
        memo[n] = result; // 缓存计算结果
        return result;
    }
}
n = 79：
未优化：调用次数达万亿级
使用记忆化：仅 157 次调用

性能

人们常说递归性能差,然而cs中你不能相信观念,而得相信profile

递归性能优于迭代的情况不在少数