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

Question

我想制作一个这样的方法,

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

我怎样才能做到这一点？将条件和方法作为参数传递的语法是什么？另外,使条件成为方法并检查它的返回值更有意义吗？

Answer 1

你的方法和Gary的答案都是完美合理的方法来重新理解对象图的递归遍历的抽象概念.但是,我看到了四个潜在的问题.不知道您的确切方案,也许这些对您来说不是问题,或者您可能应该考虑它们:

首先,假设您正在遍历的图形具有非常长的路径.您隐式地进行深度优先遍历,即使在支持尾递归的体系结构上也不能轻易地使尾递归,因此您可能会遇到调用堆栈耗尽的风险.

其次,你假设图是非循环的; 如果图形是循环的,那么你肯定会耗尽堆栈空间.

第三,我不明白为什么遍历算法返回一个实体.为什么这个方法无效？或者,如果您使用return作为累加器来累积遍历计算的值,那么为什么递归步骤不会对返回的实体执行某些操作？

第四,你似乎在这里关注的问题很糟糕.调用者负责确定(1)图的根是什么,(2)如何处理每个节点.但被调用者负责(3)确定要递归的对象.这对我来说似乎很奇怪.来电者提供了起点; 呼叫者不应该对如何继续前进有一些发言权吗？

我一般都解决这个问题如下:

• 使用在堆上分配的显式堆栈而不是使用调用堆栈来控制流
• 跟踪我之前访问过的节点,不再重新访问它们
• 让调用者确定对象何时具有可遍历的子节点.如果呼叫者希望遍历在基本情况下"触底",则呼叫者可以返回一组空子.

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

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