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

I've been doing this task and can't wrap my head around how to convert my for cycle to be recursive one AND find the depth of my tree. Is it even possible to cover all the tree's leaves without a for loop? Because a tree can have many branches and I am not sure how to measure the depth without the loop.

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;
        }

if anyone is wondering about the Branch class, there it is:

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;
        }
    }

I added a picture of a tree bellow and a method that creates same data structure tree:

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;
        }

[example of a tree][1] [1]: https://i.stack.imgur.com/BqYU2.png

CodePudding user response：

If you want to avoid having for loop there but keep recursive call you can use LINQ Aggregate:

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

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

CodePudding user response：

This suggestion does not use more recursion, but it lets you calculate the depth without using placeholders by utilizing .Max() from the System.Linq namespace and sending the current depth as a parameter to the recursive method.

//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));
}

Usage:

Branch tree;

//initialize tree

int depth = RecursiveMethodMeasureDepth(tree);

As suggested by dr.null in a comment to this answer, such a class-specific method could/should be implemented as a method in the Branch class.

Such an implementation could e.g. look like:

//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));
    }
}

and be called as follows:

Branch tree;

//initialize tree

int depth = tree.Depth;

Example fiddle here.