正確的方式退出遞歸循環

Question

我想編寫一個程序來識別在一個給定的N數組數組中的3個連續整數的出現，並通過刪除其他兩個數字來替換它們的中間值。 例如輸入→55 99 99 100 101 101 34 35 36 5 28 7 50 50 51 52 52 24 13 14 15 5 6 7 37 31 37 38 39 36 40 輸出→55 100 35 5 28 7 51 24 14 6 37 31 38 36 40

爲了達到這個目的，我寫了這個方法，它接受數組作爲輸入並返回修改後的數組。

//input 
int[] original = new int[] { 1, 3, 4, 5, 5, 6, 8} ; 

      List<int> lstoriginal = new List<int>(original); 
      List<int> modified = Test(lstoriginal); 

//method 
    public static List<int> Test(List<int> arrayInput) 
     { 

      for (i = 0; i < arrayInput.Count; i++) 
      { 
       if (i + 2 < arrayInput.Count) 
       { 
        if (arrayInput[i + 2] == arrayInput[i + 1] + 1 
        && arrayInput[i + 2] == arrayInput[i] + 2) 
        { 
         arrayInput.RemoveAt(i + 2); 
         arrayInput.RemoveAt(i); 
         List<int> temp = arrayInput; 
         Test(temp); 
        } 
       } 
      } 

      return arrayInput; 


     } 

Follwoing是執行步驟/結果是我analyzed-

1-最初如果測試輸入爲1，3，4，5，5，6，8

-2-當i = 1，它發現3,4,5按順序排除3和5，列表變爲1,4,5,6,8

3 - 下一次當i = 1時，它發現4,5 ，6刪除4和6，新的清單是1,5,8

4 - 我期待從循環退出時，我+ 2 < arrayInput.Count返回false，並試圖立即重試修改後的數組返回語句得到執行，而不是返回結果它再次調用測試（溫度）;聲明幾次，然後退出。請建議

Answer 1

您實際上根本不需要遞歸。刪除序列後，只需移動i即可顯着加快執行任務的速度。這是一個更簡單的功能，並且完成同樣的功能。我在數以萬計的隨機生成的無序序列上進行了測試。

public static List<int> Test2(List<int> arrayInput) 
{ 

    for (int i = 0; i < arrayInput.Count - 2; i++) 
    { 
     if (arrayInput[i + 2] == arrayInput[i + 1] + 1 
     && arrayInput[i + 2] == arrayInput[i] + 2) 
     { 
      arrayInput.RemoveAt(i + 2); 
      arrayInput.RemoveAt(i); 
      i = Math.Max(-1, i - 3); // -1 'cause i++ in loop will increment it 
     } 
    } 

    return arrayInput; 
} 

這就是說，回答您的具體問題，退出遞歸循環像你原來的最好辦法是改變你的遞歸函數的簽名，返回bool表明它是否真的所做的任何更改。當第一個沒有更改時返回，它們都可以存在，因此您撥打Test的電話可以打包在if (!Test(...)) { return; }中。

下面是完整的測試和試驗數據進行對比原來的我修改的版本：

public static void Main() 
{ 
    const int COUNT = 10000; 
    var r = new Random(); 
    int matchCount = 0; 

    var stopwatch1 = new Stopwatch(); 
    var stopwatch2 = new Stopwatch(); 

    for (int j = 0; j < COUNT; j++) 
    { 
     var list = new List<int>(100) {1}; 

     for(int k=1; k<100; k++) 
     { 
      switch(r.Next(5)) 
      { 
       case 0: 
       case 1: 
       case 2: 
        list.Add(list[k - 1] + 1); 
        break; 

       case 3: 
        list.Add(list[k - 1] + r.Next(2)); 
        break; 

       case 4: 
        list.Add(list[k - 1] - r.Next(5)); 
        break; 
      } 
     } 

     stopwatch1.Start(); 
     List<int> copy1 = Test1(new List<int>(list)); 
     stopwatch1.Stop(); 

     stopwatch2.Start(); 
     List<int> copy2 = Test2(new List<int>(list)); 
     stopwatch2.Stop(); 


     string list1 = String.Join(",", copy1); 
     string list2 = String.Join(",", copy2); 

     if (list1 == list2) 
     { 
      if (copy1.Count == list.Count) 
      { 
       Console.WriteLine("No change:" + list1); 
      } 
      else 
      { 
       matchCount++; 
      } 
     } 
     else 
     { 
      Console.WriteLine("MISMATCH:"); 
      Console.WriteLine(" Orig : " + String.Join(",", list)); 
      Console.WriteLine(" Test1 : " + list1); 
      Console.WriteLine(" Test2 : " + list2); 
     } 

    } 
    Console.WriteLine("Matches: " + matchCount); 
    Console.WriteLine("Elapsed 1: {0:#,##0} ms", stopwatch1.ElapsedMilliseconds); 
    Console.WriteLine("Elapsed 2: {0:#,##0} ms", stopwatch2.ElapsedMilliseconds); 
} 



public static List<int> Test1(List<int> arrayInput) 
{ 

    for (int i = 0; i < arrayInput.Count; i++) 
    { 
     if (i + 2 < arrayInput.Count) 
     { 
      if (arrayInput[i + 2] == arrayInput[i + 1] + 1 
      && arrayInput[i + 2] == arrayInput[i] + 2) 
      { 
       arrayInput.RemoveAt(i + 2); 
       arrayInput.RemoveAt(i); 
       List<int> temp = arrayInput; 
       Test1(temp); 
      } 
     } 
     else 
     {  // modified part: return the array 
      return arrayInput; 
     } 
    } 

    return arrayInput; 
} 

//method 
public static List<int> Test2(List<int> arrayInput) 
{ 

    for (int i = 0; i < arrayInput.Count - 2; i++) 
    { 
     if (arrayInput[i + 2] == arrayInput[i + 1] + 1 
     && arrayInput[i + 2] == arrayInput[i] + 2) 
     { 
      arrayInput.RemoveAt(i + 2); 
      arrayInput.RemoveAt(i); 
      i = Math.Max(-1, i - 3); // -1 'cause i++ in loop will increment it 
     } 
    } 

    return arrayInput; 
} 

Answer 2

請定義「無法退出」。你的意思是爲了保持無限循環？我沒有看到這個代碼發生。

它的樣子對我說：

該功能將： 步驟通過輸入，通過INT INT。檢查這個int和下一個2是否是順序的。然後刪除這個和下一個，然後將結果反饋到這個相同的函數中。然後它忽略了這可能給我們帶來的任何價值，並繼續以它的快樂方式。

你有一個輸入8,9,10 它開始通過：i = 0和所有這一切。 因此它發現8,9,10是連續的，然後它刪除8和9並將結果輸入到相同的函數中。我再次= 0：

所以我們重新開始：

你擁有了它開始逐步完成的9 輸入。 它逐步通過並發現列表中至少沒有3個值，並返回原始值。

然後我們完全忽略該結果並繼續上面的原始循環。現在我= 1，但arrayInput中只有一個東西，所以它應該結束。

從你在做什麼，我看不出有任何理由進行遞歸調用。你對結果沒有做任何事情，即使你是這樣，如果你有一個像8,9,10,10,11這樣的集合，它只會幫助你。然後第一個電話會將其調整爲9,10,11，遞歸調用將調整爲10