如何檢測遞歸調用中的無限循環？

Question

我有一個遞歸調用自己的函數，我想檢測並終止，如果進入一個無限循環，即 - 再次調用相同的問題。什麼是最簡單的方法來做到這一點？

編輯：這是函數，它將被遞歸調用x和y的不同值。如果在遞歸調用中，我想要終止對（x，y）的值。

int fromPos(int [] arr, int x, int y) 

Answer 1

如果功能純粹是功能性的，也就是沒有狀態或副作用，那麼你可以保留的參數的Set（編輯：看到你的編輯，你會保持一個集對的（X， y））它已被調用，並且每次只檢查當前參數是否在集合中。這樣，如果你很快遇到它，你可以檢測到一個循環。但是如果參數空間很大並且需要很長時間才能重複，那麼在檢測到一個循環之前，可能會耗盡內存。一般來說，你不能這樣做，因爲這是停滯的問題。

Answer 2

的一種方法是從一個電話傳遞一個depth變量到下一個，遞增每個函數調用自身一次。檢查depth不會超過某個特定的閾值。例如：

int fromPos(int [] arr, int x, int y) 
{ 
    return fromPos(arr, x, y, 0); 
} 

int fromPos(int [] arr, int x, int y, int depth) 
{ 
    assert(depth < 10000); 

    // Do stuff 

    if (condition) 
     return fromPos(arr, x+1, y+1, depth + 1); 
    else 
     return 0; 
} 

Answer 3

一個簡單的方法是執行下列操作之一：

以前的值和新的值傳遞給遞歸調用，讓你的第一步檢查，看他們是否相同 - 這可能是你的遞歸情況。

傳遞一個變量來表示該函數被調用的次數，並且任意限制它可以被調用的次數。

Answer 4

如果你想保留你的方法簽名，你可以保留幾組記錄x和y的舊值。

static Set<Integer> xs; 
static Set<Integer> ys;//Initialize this! 
static int n=0;//keeps the count function calls. 

int fromPos(int [] arr, int x, int y){ 

int newX= getX(x); 
int newY= getY(y); 
n++; 
if ((!xs.add(Integer.valueOf(newX)) && !ys.add(Integer.valueOf(newY))){ 

    assert(n<threshold); //threshold defined elsewhere. 
    fromPos(arr,newx,newy); 
} 
} 

Answer 5

看起來你可能正在處理2D數組。如果你在數組的值中有多餘的餘數，你可以用它作爲標誌。檢查它，如果標誌已經設置，則終止遞歸。然後在繼續之前設置它。

如果您在值中沒有多餘空間，您可以始終使其成爲一個對象數組。

Answer 6

您只能使用程序分析來檢測最不重要的程序。你所能做的最好的就是在你的特定情況下加入警衛，並通過深度級別的背景。檢測一般情況並區分遞歸算法的合法使用幾乎是不可能的。

Answer 7

您需要找到解決辦法，因爲正如您所問，沒有通用的解決方案。有關更多信息，請參閱Halting problem。

Answer 8

您可以使用重載的一致的簽名（這是更好的方法），也可以使用一個靜態變量：

int someFunc(int foo) 
{ 
    static recursionDepth = 0; 
    recursionDepth++; 
    if (recursionDepth > 10000) 
    { 
     recurisonDepth = 0; 
     return -1; 
    } 
    if (foo < 1000) 
     someFunc(foo + 3); 
    recursionDepth = 0; 
    return foo; 
} 

約翰Kugelman與超載答案是更好的怎麼一回事，因爲它是線程安全的，而靜態變量不是。

Billy3

Answer 9

恕我直言只有循環可以進入一個無限循環。

如果你的方法有太多的遞歸級別，JVM會拋出一個StackOverflowError。您可以使用try/catch塊捕獲此錯誤，並在出現此情況時執行您計劃執行的任何操作。