有没有办法将带计数的 for 循环变成递归循环？

Question

我一直在做这个任务，但我不能全神贯注于如何将我的 for 循环转换为递归循环并找到我的树的深度。没有 for 循环是否可以覆盖所有树叶？因为一棵树可以有很多分支，我不知道如何在没有循环的情况下测量深度。

static int RecursiveMethodMeasureDepth(Branch branch)
        {
            int value = 1;
            int highestValue = 1;
            for (int i = 0; i < branch.Count(); i++)
            {
                value = RecursiveMethodMeasureDepth(branch.GetBranch(i)) + 1;
                highestValue = value > highestValue ? value : highestValue;
            }
            return highestValue;
        }

如果有人想知道分支 class，那就是：

public class Branch
    {
        private List<Branch> branches;
        public Branch()
        {
            branches = new List<Branch>();
        }
        public void AddBranch(Branch branch)
        {
            branches.Add(branch);
        }
        public Branch GetBranch(int index)
        {
            return branches[index];
        }
        public int Count()
        {
            return branches.Count;
        }
    }

我在下面添加了一张树的图片和创建相同数据结构树的方法：

static Branch initializeTree()
        {
            Branch root = new Branch();
            Branch branch2 = new Branch();
            Branch branch3 = new Branch();
            root.AddBranch(branch2);
            root.AddBranch(branch3);
            Branch branch4 = new Branch();
            branch2.AddBranch(branch4);
            Branch branch5 = new Branch();
            Branch branch6 = new Branch();
            Branch branch7 = new Branch();
            branch3.AddBranch(branch5);
            branch3.AddBranch(branch6);
            branch3.AddBranch(branch7);
            Branch branch8 = new Branch();
            branch5.AddBranch(branch8);
            Branch branch9 = new Branch();
            Branch branch10 = new Branch();
            branch6.AddBranch(branch9);
            branch6.AddBranch(branch10);
            Branch branch11 = new Branch();
            branch9.AddBranch(branch11);
            return root;
        }

[树的例子][1] [1]: https://i.stack.imgur.com/BqYU2.png

Answer 1

如果你想避免在那里有 for 循环但保持递归调用，你可以使用 LINQ 聚合：

    static int RecursiveMethodMeasureDepth(Branch branch)
    {
        return branch
            .branches
            .Aggregate(1, (depth, b) =>
            {
                var currentDepth = RecursiveMethodMeasureDepth(b) + 1;
                return depth < currentDepth ? currentDepth : depth;
            });
    }

参考 https://docs.microsoft.com/en-us/dotnet/api/system.linq.enumerable.aggregate?view=net-6.0

Answer 2

此建议不使用更多递归，但它允许您通过使用 System.Linq 命名空间中的 .Max() 并将当前深度作为参数发送到递归方法来计算深度而不使用占位符.

//using System.Linq;

static int RecursiveMethodMeasureDepth(Branch branch, int currentDepth = 1)
{
    if (branch.Count() == 0)
    {
        return currentDepth;
    }
    
    return Enumerable.Range(0, branch.Count())
        .Max(i => RecursiveMethodMeasureDepth(branch.GetBranch(i), currentDepth + 1));
}

用法：

Branch tree;

//initialize tree

int depth = RecursiveMethodMeasureDepth(tree);

根据 dr.null in a comment to 的建议，这样的 class-specific 方法 could/should 将作为 Branch class 中的方法实现。

这样的实现可以例如看起来像：

//using System.Linq;

public class Branch
{
    //Other properties and methods

    public int Depth => GetDepth();
    
    private int GetDepth(int currentDepth = 1)
    {
        if (!branches.Any())
        {
            return currentDepth;
        }
        
        return branches.Max(branch => branch.GetDepth(currentDepth + 1));
    }
}

并调用如下：

Branch tree;

//initialize tree

int depth = tree.Depth;

示例 fiddle here.

有没有办法将带计数的 for 循环变成递归循环？

Is there a way to turn a for loop with count into recursive one?

c#

tree

recursion

loops