递归实验

Question

我正在尝试递归，以便掌握其中的概念。它与语言无关，因此同样的概念也适用于C#和Java。

我有一个包含多个节点的TreeView。我想遍历每一个节点，并计算满足特定条件的节点。如果在任何时候不满足条件，我希望算法最终返回-1。

每个TreeViewItem只有在它有一个名为“Tag”的条件时才会被考虑(总共有3种类型的TreeViewItems -我只考虑"Condition“类型)。

一旦发现一个条件是“TreeViewItem”类型的，我想检查一下它是否满足某个条件。正如我前面提到的，即使只有一个TreeViewItem不满足条件，我也希望算法最终返回-1。

如果算法没有返回-1，我希望它返回它找到的有效条件的数量-即每次成功通过条件时，将递增一个整数，并在结束时返回最终计数。

这就是我到目前为止所尝试的：

private int CountConditions(TreeViewItem item)
        {
            int conditionCount = 0;

            foreach (TreeViewItem child in item.Items)
            {
                int previousCount = CountConditions(child);

                if (previousCount == -1)
                {
                    return -1;
                }
                else
                {
                    return conditionCount += previousCount;
                }
            }

            if (item.Tag.Equals("Condition"))
            {

                if (/*Condition is not satisfied*/)
                {
                    return -1;
                }
                else
                {
                    return conditionCount++;
                }
            }
            else
            {
                return conditionCount;
            }
        }

如果条件不满足，我当前的算法实际上返回-1，但是如果条件满足，它只返回0，而不是有效条件的数量。

Answer 1

这不是一个简单的递归，因为您必须同时处理错误条件和正常条件。如果你没有错误条件，只需要计算条件节点的数量，你可以这样写：

private int CountConditions(TreeViewItem item)
{
    int currentCondition = CalculateCondition(item)
    int childCounts = 0;
    foreach (TreeViewItem child in item.Items)
    {
        int childCount = CountConditions(child);
        childCounts += childCount;
    }
    return currentCondition + conditionCounts
}

private int CalculateCondition(TreeViewItem item)
{
    if (item.Tag.Equals("Condition"))
        return 1;
    else
        return 0;
}        

但要处理错误，您必须对错误条件进行两次检查，一次针对当前节点，另一次针对子节点，如果遇到该条件，则立即返回：

int error = -1

private int CountConditions(TreeViewItem item)
{
    int currentCondition = CalculateCondition(item)
    if (currentCondition == error) // new
        return error;              // new
    int childCounts = 0;
    foreach (TreeViewItem child in item.Items)
    {
        int childCount = CountConditions(child);
        if (childCount == error)   // new
            return error;          // new
        childCounts += childCount;
    }
    return currentCondition + conditionCounts
}

private int CalculateCondition(TreeViewItem item)
{
    if (item.Tag.Equals("Condition"))
        if (((item.Header as StackPanel).Children[2] as TextBox).Text.Equals("")) // new
            return error; // new
        else              // new
            return 1;
    else
        return 0;
}

Answer 2

您可以使用

return conditionCount++;

这是一种糟糕的做法。有很好的理由。这里发生的情况是a)返回conditionCount (设置为0)b)递增conditionCount

B永远不会出现在return语句之后，所以您总是将0传递给您的下一个递归步骤。

您可以使用

return ++conditionCount;

或者更好

conditionCount++;
return conditionCount;

Answer 3

您应该只在函数的末尾执行return conditionCount;。只有return -1;必须在函数的中间。