如何动态地将条件和方法传递给递归方法

本文关键字：方法 递归方法 条件 何动态 动态 | 更新日期: 2023-09-27 18:12:19

我想创建一个这样的方法，

public dynamic Traverse(dynamic entity, conditions, method)
{
    foreach (var propInfo in GetTraversableProperties(entity))
    {
        if (condition) method(propInfo.GetValue(etc));
        Traverse(propInfo, condition, method);
    }
    return entity;
}

我该怎么做?将条件和方法作为参数传递的语法是什么?另外，将条件作为方法并检查它的返回值是否更有意义?

如何动态地将条件和方法传递给递归方法

您的方法和Gary的回答都是将对象图递归遍历的抽象概念具体化的非常合理的方法。然而，我看到了四个潜在问题。在不知道具体情况的情况下，也许这些对您来说不是问题，或者您应该考虑它们:

首先，假设你要遍历的图有非常长的路径。您隐式地执行深度优先遍历，并且即使在支持尾部递归的体系结构上，您的方法也不能轻松地进行尾部递归，因此您冒着耗尽调用堆栈的风险。

第二，假设图是无环的;如果图是循环的，那么你肯定会耗尽堆栈空间。

第三，我不明白为什么遍历算法返回一个实体。为什么这个方法不是无效的?或者，如果您使用返回作为累加器来累加遍历计算的值，那么为什么递归步骤不对返回的实体做一些事情呢?

第四，你似乎没有把关注点分开。调用者负责确定(1)图的根是什么，(2)如何处理每个节点。但是被调用者负责(3)找出要递归的对象。这在我看来很奇怪。调用者提供起始点;打电话的人难道不应该对如何继续通话有一些发言权吗?

我一般是这样解决这个问题的:

  • 使用在堆上分配的显式堆栈，而不是为控制流使用调用堆栈
  • 跟踪我以前访问过的节点，不要重新访问它们
  • 让调用者确定对象何时具有可遍历的子对象。如果调用者希望遍历在基本情况下"bottom out"，那么调用者可以返回一组空的子元素。

如果我想要一个累加器，我可能会实现像这样的草图:

static R DepthFirstGraphAccumulate<T, R>(
    T root, 
    Func<T, IEnumerable<T>> children, 
    Func<T, R, R> accumulate)
{
    var accumulator = default(R);
    var visited = new HashSet<T>();
    var stack = new Stack<T>;
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        if (!visited.Contains(current))
        {
            visited.Add(current);
            foreach(var child in children(current))
                stack.Push(child);
            accumulator = accumulate(current, accumulator);
        }
    }
    return accumulator;
}

因此，例如，如果我有一个整数图，我希望从一个特定的起始节点求和可到达的节点，我会说:

int total = DepthFirstGraphAccumulate<Node, int>(
    startNode, 
    node=>node.NeighbouringNodes, 
    (node, sum)=>node.Value + sum);

然而，我很想在"让我们分开关注点"的道路上更进一步，说，嘿，让我们写一个抽象的遍历器:

static IEnumerable<T> DepthFirstGraphTraversal<T>(
    T root, 
    Func<T, IEnumerable<T>> children)
{
    var visited = new HashSet<T>();
    var stack = new Stack<T>;
    stack.Push(root);
    while(stack.Count != 0)
    {
        var current = stack.Pop();
        if (!visited.Contains(current))
        {
            visited.Add(current);
            foreach(var child in children(current))
                stack.Push(child);
            yield return current;
        }
    }
}

现在如果我想对图中的每个节点做一些操作，我只需输入:

foreach(var node in DepthFirstGraphTraversal<Node>(startNode, n=>n.NeighbouringNodes))
     DoSomething(node);

如果我想表达"对每个符合条件的节点做一些事情"的概念，那么我会写:

var nodes = from node in DepthFirstGraphTraversal<Node>(startNode, n=>n.NeighbouringNodes)
            where condition(node)
            select node;
foreach(var matchingNode in nodes) DoSomething(matchingNode);

我认为使用Func委托的条件是有意义的。至于如何传递方法，这将再次使用委托。我会这样做:

public dynamic Traverse(dynamic entity, Func<dynamic, bool> conditions, Action<dynamic> method)
{
    foreach (var propInfo in GetTraversableProperties(entity))
    {
        if (conditions(entity)) method(propInfo.GetValue(etc));
        Traverse(propInfo, conditions, method);
    }
    return entity;
}

Func: http://msdn.microsoft.com/en-us/library/bb549151.aspx

操作:http://msdn.microsoft.com/en-us/library/018hxwa8.aspx

相关文章：