Java：記住遞歸方法的前一步的結果

我正在研究Boggle遊戲，有些人告訴我搜索單詞的最佳方法是使用遞歸。我正在嘗試使用searchWord方法來搜索單詞。如果找到第一個字母，該方法將自行調用並刪除第一個字母。當長度== 0（找到字）或false（未找到字母）時，該方法返回true。問題有時會在一個「骰子」中多次出現相同的字母......爲了解決這個問題，我需要計算該字母，如果它不止一次出現，它應該搜索該字母的下一個外觀（搜索同一個字不丟棄第一個字母）。我需要一種方法來記住該字母和多個字母所圍繞的字母索引，以便在未找到該字母時檢查是否還有其他可能性。由於這是一個遞歸方法，我不知道如何將這些放在一個變量中，因爲只要方法調用它們，它們就會被更改...Java：記住遞歸方法的前一步的結果

希望你們可以幫忙！這裏的方法：

public boolean searchWord(String word, int i, int j) { 
    boolean res; 
    if (word.length() == 0) { 
     res = true; 
    } else { 
     String theWord = word.toUpperCase(); 
     int[] indexes = searchLetter(Character.toString(theWord.charAt(0)), i, j); 
     if (indexes[0] > -1) { 
      res = searchWord(theWord.substring(1), indexes[0], indexes[1]); 
     } else if(countLetter(Character.toString(/*The value that has to be memorized*/), /*index 1 that has been memorized*/, /*index 2 that has been memorized*/) > 1) { 
      res = searchWord(theWord, i, j); 
     } else { 
      res = false; 
     } 
    } 
    return res; 
}

注：是的，我使用字符串這是奇怪，因爲字符可能是一個更好的選擇，但以後我可能會改變。

來源

2013-01-22 E. V. d. B.

你應該重寫這個來使用堆棧。使用堆棧遞歸幾乎總是更好。然後，您可以存儲一些關於上下文的信息，並將其推送到需要更多處理的堆棧上，並在您準備好處理它們時彈出。

來源

2013-01-22 22:43:32 Rob

我寄給我的老師，他說，這是最好的完成遞歸，儘管這很困難。我還沒有真正瞭解過堆棧，或者我不明白你的意思。我仍然是初學者（在學校只有3-4個月的java）：s –

好的。那麼讓我來幫助遞歸。遞歸的問題是你沒有存儲你所在的任何框架。堆棧是使用LIFO（後進先出）的數據結構：將事物推入堆棧，然後將其彈出。舉例來說，如果你編寫一個解析器，一個Stack允許你維護你想要的關於你在AST（抽象語法樹）中構造的每個節點的上下文信息。 – Rob

由於以下幾個原因，Rob的投訴並不一般。首先，在許多情況下，遞歸是代碼清晰度方面更優雅的方式。其次，使用堆棧（是的，呼叫推送也是方法調用）時，調用方法調用非常便宜。 – Dan

只需在您的方法中添加另一個參數即可。例如，您可以創建一個只保存字母和int的對象。由於Java在進行遞歸調用時只傳遞對該對象的引用（但不會複製對象本身），因此參數將始終指向同一對象。你可能想要使用Java的pair類（如果我沒有記錯，它在地圖中使用）。

來源

2013-01-22 22:47:11 Dan

但是我不能只是廣告'String previous = word'吧？因爲這會改變每一個電話？因爲我不太明白你的意思：s –

向我們展示你的優雅代碼，Dan。隨意添加一個LISP版本。 – Rob

原則上，您可以傳遞任何此類值作爲附加參數。這樣，參數/調用堆棧就像你的堆棧一樣。

來源

2013-01-22 22:50:37

目標：以查看是否在驚奇板存在

假設一個字：

每個位置（即立方體）只能每字使用一次
每個字母必須相鄰（垂直，水平或對角）

這裏是我的僞代碼遞歸做這樣的嘗試（其中驚奇板是字符的二維數組 - 這應該已經與字符填充之前調用此方法）：

// searches for a single occurence of a word on the boggle board 
boolean searchWord(String word, char[][] board) 
    for each position on the board (x,y) 
     boolean[][] visited = new boolean[width][height] // all false 
     if (searchWord(x,y,board,visited)) 
      return true 
    return false 

// searches a position on the board 
boolean searchWord(String word, int x, int y, char[][] board, boolean[][] visited) 
    if x and y are valid (0 >= x < width and 0 >= y < height) 
     if visited[x][y] == false 
      visited[x][y] = true 
      if the letter at x,y equals the 1st char of the search word 
       if word.length() == 1 
        return true 
       else 
        for each surrounding position (x2, y2) 
         if searchWord(word.substring(1),x2,y2,board,visited) 
          return true 
    return false

正如你所看到的遞歸是路徑尋找的好選擇（發現單詞）。你只需要傳遞當前狀態（在這種情況下爲visited），這樣你就知道你已經在哪裏了。

我已經使用參數來存儲狀態，但如果您真的想要使用實例變量。我會建議使用參數，因爲它與函數式編程範例一致，並且不太可能遭受意想不到的副作用。

顯式使用堆棧在這裏並不是真的需要。如果值爲scope（像Java中的局部變量），並且應該按特定順序訪問，堆棧非常棒，這在這裏沒有什麼幫助。通過使用遞歸你通過使用Java的調用堆棧無論如何，如果你不小心，你可以永久遞歸，你會得到一個StackOverflowException;）

來源

2013-01-22 23:30:46

聽起來不錯！儘管我想嘗試一下，但我不確定我應該怎樣處理你的代碼，但我不確定填充「每個周圍位置」這樣的地方是什麼：s –

Java：記住遞歸方法的前一步的結果

回答

相關問題