如何編寫一個遞歸方法來返回包含令牌的文件中的所有行字符串

Question

我的教授給了我們一個任務來編寫一個執行很多事情的程序。具體的這個程序中的一件事是通過一個.txt文件，並返回你指定的單詞的所有實例和它們所在的行。例如，如果這是文本文件：

這是一個測試。
測試word文件。
這將被視爲測試。

運行方法和搜索詞後，「測試」，你應該接收回來的東西，如：

1: This is a test.  
3: This will be considered a test. 

現在，這是我的問題。他希望我們用遞歸方法來做，而且我不知道如何啓動該方法。我知道一個遞歸方法，你必須調用它自己並減少每次你調用它，但是，這個方法的參數是一個單詞。說我有：

String getTheWord (String word) {  
    if (word == 0){ //which still wouldn't compile, so I think I should use word == null  
     // something  
    } 

    //something smart here  

    return getTheWord(word - 1); // which wouldn't compile 
} 

那麼我應該怎麼寫呢？我想我必須使用一個字符串作爲參數，因爲我怎麼才能知道我要找的字是什麼？或者，也許我錯了，任何幫助！

Answer 1

嘗試類似：

public String getTheWord(String textToSearch, String searchingFor, 
    int currentLineNumber) { 

    // Separate the text into lines. 
    String[] lines = textToSearch.split('\n'); 

    // Get the first line of the (remaining) text. 
    String firstLine = lines[0]; 

    // We're going to have some result from this method call: either 
    // an empty string or a message indicating that we found the word. 
    String resultFromThisLine = "";   

    // Now, look for the word. 
    if (firstLine.contains(searchingFor)) { 
     // We found it. 
     resultFromThisLine = currentLineNumber + ": " + firstLine + "\n"; 
    } 

    // Now we check to see if there are any lines left. 
    if (lines.length == 1) { 
     // This was the last line. 
     return resultFromThisLine; 
    } else { 
     // There are more line(s). 
     // Create a string with all lines but the first one. 
     String remainingLines = ""; 
     for (int i=1; i<lines.length; i++) { 
      remainingLines += lines[i] + "\n"; 
     } 


     // Here's the key part. 
     // Take the result from this line, add it to the result from the 
     // next line, and return *that*. 

     return resultFromThisLine + getTheWord(remainingLines, searchingFor, 
      currentLine + 1); 

    } 
} 

Answer 2

首先我們要問，爲什麼我們要使用遞歸解決這個問題的。在Introduction to Computer Science - Java頁面，我們可以發現一些特點，它描述遞歸解決方案：

1. ，我們有一個解決方案和一個返回值的簡單的基本情況。
2. 讓我們的問題更接近基本案例的一種方法。即一種方式 砍掉問題的一部分，以得到一個更簡單的問題。
3. 遞歸調用將簡單問題傳遞迴 方法。

對我來說，你的問題根本不符合這個特性。

但是，好吧，你不想這樣做 - 你必須。

首先你應該考慮模型，它可以代表你的問題。我創建了簡單的Line類，它存儲行號和行。

class Line { 

    private int number; 
    private String text; 

    public Line(int number, String text) { 
     this.number = number; 
     this.text = text; 
    } 

    public int getNumber() { 
     return number; 
    } 

    public String getText() { 
     return text; 
    } 

    @Override 
    public String toString() { 
     return number + " : " + text; 
    } 
} 

然後，你應該使用簡單循環創建解決方案。

class LoopSearcher { 

    public List<Line> findLines(String text, List<String> lines) { 
     List<Line> matchLines = new ArrayList<Line>(); 
     int index = 0; 
     for (String line : lines) { 
      index++; 
      if (line.contains(text)) { 
       matchLines.add(new Line(index, line)); 
      } 
     } 
     return matchLines; 
    } 
} 

您可以用這種方式進行測試：

List<String> lines = IOUtils.readLines(new FileInputStream(new File(
     "D:/test.txt"))); 

List<Line> loopLines = new LoopSearcher().findLines("test", lines); 

for (Line line : loopLines) { 
    System.out.println(line); 
} 

現在，我們有循環的解決方案，我們可以修改成遞歸解決方案：

class RecursiveSearcher { 

    LinkedList<Line> matchLines = new LinkedList<Line>(); 

    public List<Line> findLines(String text, List<String> lines) { 
     if (lines.isEmpty()) { 
      return matchLines; 
     } 

     int number = lines.size() - 1; 
     String line = lines.remove(number); 
     if (line.contains(text)) { 
      matchLines.addFirst(new Line(number + 1, line)); 
     } 
     return findLines(text, lines); 
    } 
} 

你可以測試它這樣：

List<String> lines = IOUtils.readLines(new FileInputStream(new File(
     "D:/test.txt"))); 

List<Line> recursiveLines = new RecursiveSearcher().findLines("test", 
     lines); 
for (Line line : recursiveLines) { 
    System.out.println(line); 
} 

就像你看，我有創建方法與將參數：

1. 文本 - 文本，我們要在每行找到
2. 線 - 文件中的所有行的列表。當然，您可以提供原始String，它可以表示所有文件內容。