在递归中避免Stackoverflow的技巧

-2

我正在为ASP.NET/C＃网站编写一个算法，用于为学生，教师和课堂室计划一个时间表。我做这做递归这样的（伪代码）：在递归中避免Stackoverflow的技巧

public Booking GetBooking(..., ref numberOfTries) { 
    numberOfTries--; 
    if (numberOfTries == 0) { 
      return null; 
    } 

    if (allResorcesAreAvailable) { 
      return new Booking() 
    } 

    // Try next time slot 
    return GetBooking(..., ref numberOfTries); 
}

正如你可以看到我有一个确保递归从来没有失控（numberOfTries）的手柄。然而，随着时间的推移，该算法必然会尝试很多次，并导致Stackoverflow异常。有关如何避免这种情况的任何建议？增加堆栈大小（我不喜欢这个）？在线程中运行计划？我已经在考虑重写整个方法，但只是想看看是否有人可以提供一些建议。

来源

2016-08-14 nath

递归是一个美丽而雄辩的想法，但我觉得如果难以管理。我会重写它，因为我是一个简单的女孩，我喜欢简单易维护的代码。我唯一看到错误的是numberOfTries可能没有向上约束的可能性。 – Missy

代码中没有什么使得递归有用。一个简单的循环可以取代这个。 –

这可能只是一个风格的建议，因为我不知道输入的范围，但如果你确实需要做递归，而不是有numberOfTries--在开始时你可以通过改变return语句来接近你的基本情况：如果输入为0，则返回GetBooking（...，ref numberOfTries-1）以避免堆栈溢出。但就像上面的评论所说的，从所显示的内容看，它们不需要递归。 –

该问题是通过从递归转移来解决的，而是将其写成一个简单的循环/迭代。我解决了这样的问题：

public Booking GetBooking(..., int numberOfTries) { 
    while (true) 
      numberOfTries--; 
      if (numberOfTries == 0) { 
       return null; 
      } 

      if (allResorcesAreAvailable) { 
       return new Booking() 
      } 
    } 
}

来源

2016-08-14 17:18:16 nath

通常写成for循环：for（int t = 0; t

-1

我应该注意，从你发布的代码，你似乎可以用简单的循环设计。

但我会解决实际问题“如何防止递归StackOverflow”。递归做

任何东西都可以用一个简单的Stack完成，
同时用Stack，你可以把它的堆和几乎没有限制管理它......

让把你的代码，会像这样

public Booking GetBooking(..., int numberOfTries) 
{ 
Stack<BookingStateData> stk = new Stack<BookingStateData>(); 

while(!stk.isEmpty()) 
{ 
    BookingStateData current = stk.Pop(); 

    if (current.allResorcesAreAvailable) { 
    return new Booking(current...) 
    } 

    if(stk.Count > maxDepth) // if you want to limit the DFS Depth 
    continue; 

    stk.push(new BookingStateData(yada,yada)); // fake recursion. 
} 
return null; 
}

新增注：如果您使用Queue代替Stack的，你可以使用BFS方法，而不是给DFS。

来源

2016-08-14 17:28:56

在递归中避免Stackoverflow的技巧

回答

相关问题