如何擺脫這個循環

Question

我正在處理項目歐拉數5.我沒有谷歌搜索，因爲這通常會導致與答案的SO。所以，這是我得到的：

private int Euler5(int dividend, int divisor) 
    { 
     if (divisor < 21) 
     { 
      // if it equals zero, move to the next divisor 
      if (dividend % divisor == 0) 
      { 
       divisor++; 
       return Euler5(dividend, divisor); 
      } 
      else 
      { 
       dividend++; 
       return Euler5(dividend, 1); // move to the dividend 
      } 
     } 
     // oh hey, the divisor is above 20, so what's the dividend 
     return dividend; 
    } 

在我看來，這是有道理的。然而，VS2012給了我一個StackOverFlowException，表明我確保我沒有處於無限循環或使用遞歸。我的問題是，爲什麼這是一個無限循環？我有一種感覺，我錯過了一件完全愚蠢的事情。

編輯

由於人們似乎保持張貼，我要重申的是，我沒有使用谷歌，怕跌倒的答案。我不想要這個問題的答案。我只想知道爲什麼我得到這個例外。

Answer 1

當然這種邏輯會打擊堆棧。想想這個，如果你要實現這個邏輯來解決找到可以被1-10整除的最小數字的問題，那麼你至少要在堆棧中調用2520個調用深度：problem statement：

2520是可以被1到10中的每個數字除以沒有餘數的最小數字。

對於1--20，答案顯然要大得多，而且你吹的堆棧也不足爲奇。你應該找到一個非遞歸解決方案。

我的問題是，爲什麼這是一個無限循環？

不是。這個堆棧的大小是有限的。您正在進行太多的遞歸調用，並最終違反最大堆棧大小。

我有一種感覺，我錯過了一件完全愚蠢的事情。

您來到right place。

Answer 2

+1對於Jason的回答，這清楚地解釋了問題。

現在爲一些解決方案！我知道至少有三種方法可以從算法中去除遞歸：

1. 找到一個純粹的迭代算法（對於某些問題可能很難）;
2. 將遞歸算法轉換爲具有循環的類似算法，並使用堆棧（或某種列表）存儲等價的調用堆棧。這與原來的空間需求相似，但堆可以比堆棧增大得多！
3. 一個特殊的遞歸算法家族是尾遞歸。這些可以很容易地機械地改變，永遠不會溢出堆棧。你很幸運，這是你的情況！

算法是尾遞歸如果所有的遞歸調用都尾通話，這意味着它們在返回前做的最後一件事。如果你不清楚，查找更好的例子與谷歌。

這樣的算法可以很容易地通過調整參數和使用goto而不是真正的調用來轉換。再看看你的例子：

private int Euler5(int dividend, int divisor) 
{ 
    tail_call: 
    if (divisor < 21) 
    { 
     // if it equals zero, move to the next divisor 
     if (dividend % divisor == 0) 
     { 
      divisor++; 
      goto tail_call; // return Eular5(dividend, divisor); 
     } 
     else 
     { 
      dividend++; 
      // return Eular5(dividend, 1); // move to the dividend 
      divisor = 1; 
      goto tail_call; 
     } 
    } 
    // oh hey, the divisor is above 20, so what's the dividend 
    return dividend; 
} 

哦，嘿！它的功能完全相同，但是具有固定的堆棧大小（沒有調用，只有跳轉）。 現在有人會說：「呃... gotos！他們是邪惡的！死了，死了！」我會說這是少數合法用途之一。畢竟，如果你的編譯器足夠聰明，它會自己做尾部調用優化（F＃實際上，C＃沒有，JIT可能在x64上執行，而不是在x86上執行）。

但是對於那些人我會說：看起來好一點。因爲每個if/else分支的末尾都有一個goto，所以我可以將它完全移到「if」之外。現在我有類似「start：if（X）{Y（）; goto start;}」想一想，它只是一個「while（X）Y（）」循環。所以你只是發現你的功能的迭代版本：

private int Euler5(int dividend, int divisor) 
{ 
    while (divisor < 21) 
    { 
     // if it equals zero, move to the next divisor 
     if (dividend % divisor == 0) 
     { 
      divisor++; 
     } 
     else 
     { 
      dividend++; 
      divisor = 1; 
     } 
    } 
    // oh hey, the divisor is above 20, so what's the dividend 
    return dividend; 
} 

不錯！