遞歸和StackOverflow - 我應該用什麼來代替？

我有一段代碼：遞歸和StackOverflow - 我應該用什麼來代替？

private void colorize(int color, int x, int y) { 
    visited[x][y] = true; 
    if (x + 1 < d) 
     if (board[x + 1][y] == board[x][y] && visited[x + 1][y] == false) 
      colorize(color, x + 1, y); 
    if (x - 1 >= 0) 
     if (board[x - 1][y] == board[x][y] && visited[x - 1][y] == false) 
      colorize(color, x - 1, y); 
    if (y + 1 < d) 
     if (board[x][y + 1] == board[x][y] && visited[x][y + 1] == false) 
      colorize(color, x, y + 1); 
    if (y - 1 >= 0) 
     if (board[x][y - 1] == board[x][y] && visited[x][y - 1] == false) 
      colorize(color, x, y - 1); 
    board[x][y] = color; 
}

我把它叫做：colorize(int random, int 0, int 0)。即使是一張小桌子（20x20），這也給我提供了stackoverflow。我怎樣才能做到這一點沒有遞歸？

來源

2012-11-08 Mateusz Kaflowski

我看不到對d的引用。什麼是d？ –

將遞歸算法轉換爲迭代算法。 –

通常，一個計算器會顯示您錯過了一個基本情況。您應該使用調試器（或適當的SOP語句）運行此代碼以查找問題。 –

給出的代碼似乎很好。

有，以什麼d是一個問題，但我猜想，這是正確的方形格柵的寬度。

這有可能是你在任何代碼調用這是一個問題，但你的代碼給了我們不應該有一個堆棧溢出。

大廈關閉芒Rolandi丹尼爾森的答案，這裏是一個不使用明確的堆棧，但建立一個在堆上。我的java非常生疏，但這應該工作。如果有人對此代碼進行了修復，請隨時修復此問題。

非但沒有堆棧溢出，在大表的大小，我得到一個java.lang.OutOfMemoryError: Java heap space錯誤信息。您可以使用一組或其他一些數據結構（而不是鏈接列表）來優化內存使用情況。

import java.util.Queue; 
import java.util.LinkedList; 

class Pair<L,R> { 
    private L l; 
    private R r; 

    public Pair(L l, R r){ 
     this.l = l; 
     this.r = r; 
    } 

    public L getL(){ return l; } 
    public R getR(){ return r; } 
} 


public class HelloW { 
    static int d = 20; 
    static boolean[][] visited = new boolean[d][d]; 
    static int[][] board = new int[d][d]; 

    static Queue<Pair<Integer, Integer>> Q = new LinkedList<Pair<Integer, Integer>>(); 

    static void colorize(int color, int orig_x, int orig_y) { 
     Q.add(new Pair<Integer, Integer>(orig_x, orig_y)); 

     while (Q.isEmpty() == false) { 
      Pair<Integer,Integer> foo = Q.remove(); 
      int x = foo.getL(); 
      int y = foo.getR(); 
      int old_color = board[x][y]; 

      visited[x][y] = true; 
      board[x][y] = color; 

      if (x + 1 < d) 
       if (board[x + 1][y] == old_color && visited[x + 1][y] == false) 
        Q.add(new Pair<Integer, Integer>(x+1, y)); 
      if (x - 1 >= 0) 
       if (board[x - 1][y] == old_color && visited[x - 1][y] == false) 
        Q.add(new Pair<Integer, Integer>(x-1, y)); 
      if (y + 1 < d) 
       if (board[x][y + 1] == old_color && visited[x][y + 1] == false) 
        Q.add(new Pair<Integer, Integer>(x, y+1)); 
      if (y - 1 >= 0) 
       if (board[x][y - 1] == old_color && visited[x][y - 1] == false) 
        Q.add(new Pair<Integer, Integer>(x, y-1)); 
     } 
    } 

    public static void main (String[] args) { 
     colorize(1, 0, 0); 
    } 
}

來源

2012-11-08 23:11:16

工作偉大！謝謝。你很精彩:) –

我只是複製您的代碼並運行它像下面你可以看到，它的作品完美，用矩陣十足的「真實」的和矩陣滿者的結束：

static int d = 20; 
static boolean[][] visited = new boolean[d][d]; 
static int[][] board = new int[d][d]; 

static void colorize(int color, int x, int y) { 
    visited[x][y] = true; 
    if (x + 1 < d) 
     if (board[x + 1][y] == board[x][y] && visited[x + 1][y] == false) 
      colorize(color, x + 1, y); 
    if (x - 1 >= 0) 
     if (board[x - 1][y] == board[x][y] && visited[x - 1][y] == false) 
      colorize(color, x - 1, y); 
    if (y + 1 < d) 
     if (board[x][y + 1] == board[x][y] && visited[x][y + 1] == false) 
      colorize(color, x, y + 1); 
    if (y - 1 >= 0) 
     if (board[x][y - 1] == board[x][y] && visited[x][y - 1] == false) 
      colorize(color, x, y - 1); 
    board[x][y] = color; 
} 

public static void main(String[] args) 
{ 
    colorize(1, 0, 0); 
}

編輯：測試程序在我的電腦上正常運行d = 20，但是如果我增加到d = 100，我得到StackOverflow。看起來算法或多或少，但遞歸沒有多大意義，應該有更優雅的表達方式。

來源

2012-11-08 23:13:40 mxns

我想你有更多的內存分配給你的JVM –

它在幾毫秒內完成，難道不需要很多時間來遞歸填充我認爲的內存？另外，看看代碼似乎很好 – mxns

@RununAgarwal對不起，你是對的！如果我增加到d = 100，我會發現溢出。我需要更仔細地看。 – mxns

就我所知，您的代碼正常工作;唯一可能影響它的是如果另一個線程在遞歸過程中來到並修改了其中一個數據結構，或者在發佈之前已經過度簡化了它。

來源

2012-11-08 23:15:27

遞歸和StackOverflow - 我應該用什麼來代替？

回答

相關問題