递归方法的良好设计模式？

Question

我正在写一个方法，它接受一个检查其值的变量，并递归地调用它自己以获取其中的所有属性。还有集合属性和集合中的集合。

问题是，当变量是一个非常复杂的对象，递归失败我的应用程序堆栈溢出错误，我明白。

我的问题是当我面对这样的情况时，避免错误的最佳设计是什么。

btw我正在做这个审计。

Answer 1

大多数递归方法可以写为Depth First Search像这样：

DFS递归方式：

public Result recursiveMethod(Node current, Result currentResult) 
{ 
    // --- aggregate result 
    currentResult = Aggregate(currentResult, currrent.value); 

    // --- returns children nodes from the current one 
    var children = GetChildren(current); 

    foreach(var child in children) 
    { 
     // --- recursive call and store new result 
     currentResult = recursiveMethod(child, currentResult); 
    } 

    return currentResult; 
} 

DFS非递归（迭代）的方式：

public Result loopMethod(Node init) 
{ 

    var result = default(Result); 
    var inputs = new Stack<Node>(); 
    inputs.Push(init); 

    while(inputs.Any()) 
    { 
     var current = inputs.Pop(); 

     // --- aggregate result 
     result = Aggregate(result, current.value); 

     // --- returns children nodes from the current one 
     var children = GetChildren(current); 

     // --- push new nodes onto stack (you can think of this as the "recursive call") 
     foreach(var child in children) 
     { 
      inputs.Push(child); 
     }    
    } 

    return result; 
} 

这是也有帮助的是，您可以使用迭代方式实现Breadth First Search，通过将“Stack”替换为“Queue”（并使用“Enqueue”/“Dequeue”来代替“推”/“流行”）。使用递归实现BFS将非常困难。

编辑：

@阿列克谢的回答让一些伟大的意见在你为什么会遇到一个堆栈溢出异常的一些潜在原因。总之，请确保以下各项为真：

1. 你的递归（或环）必须进步。换句话说，它应该明显达到目的。

2. 导致永无止境的递归的最常见的错误之一是让一个已经访问过的节点滑入，最终导致永久循环。使用Set来存储访问节点是确保不会发生这种情况的好方法，但请记住，存在一定的内存开销。

底线：

做如此大规模的迭代是要花费你 - 无论是在栈资源和/或在内存中。问问自己这是否是完成这项任务的正确的地点和策略。此外，如果您对数据结构有一些了解（无论是非常深入还是非常广泛），您可以通过明智地选择DFS或BFS来优化内存优化。

Answer 2

尽管有时递归比循环更清晰，但我认为如果它溢出了你的栈，那么你的有使用一个循环。

或者，您可以检查自己调用了多少次。就像这样：

private int recursionCount = 0; 
public void method() { 
    recursionCount++ 
    if (recursionCount > 10000) { 
     //do something to handle this situation 
     //maybe return 
    } 
    method(); 
} 

我的意思是，如果你要递归了这么多次，它可能是一个错误或设计错误。重新思考问题并重新设计。

Answer 3

如果您的递归函数与国有企业的失败，有三种可能的原因：

1. 你的对象图是太大了。这是可能的，但不太可能。为了解决这个问题，你应该重写你的函数来使用Stack<T>和一个循环。这样您将使用堆而不是调用堆栈来将路径存储回原始对象。
2. 你的函数有语义错误。确保首先写入非递归案例，并确保每次都肯定可以访问它。可能存在一些细微的错误，例如所有对象（包括它们自己）上存在的属性。
3. 您的对象图有周期。我认为这是最可能的原因。您从对象A开始，并在更深层次上再次找到A。为了解决这个问题，你需要使用遍历对象的缓存并将其从调用传递到调用，HashSet<T>将工作正常。检查你的当前对象是否存在于散列集中将成为一个额外的非递归情况。