在遞歸中避免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的技巧

回答

相關問題