不能停止遞歸java

我試圖通過使用它的標籤來搜索節點，並在目標節點下添加一個新節點，當我嘗試使用遞歸來搜索它時，它總是返回一個錯誤的目標或返回null。任何人都知道如何解決它？不能停止遞歸java

public TreeNode getNodeReference(String label){ 

    if(left!=null){ 
     if(check(left,label)==true) 
      return left; 
     left.getNodeReference(label); 
    } 

    if(middle!=null){ 
     if(check(middle,label)==true) 
      return middle; 
     middle.getNodeReference(label); 
    } 
    if(right!=null) 
    { if(check(right,label)==true) 
      return right; 
     right.getNodeReference(label); 
    } 
    return null; 
} 


public boolean check(TreeNode tree,String label){ 

    if(tree.getLabel().equals(label)) 
     return true; 
    else return false; 
}

來源

2013-08-06 wah725

您的一般問題是，您遞歸地調用方法，但根據結果不做任何事情。因此，當您調用left.getNodeReference（）時，將結果保存在變量中並將其與空值進行比較。如果它非空，則返回結果 - 完成。否則，繼續前進。中間和右邊一樣。 –

如果你實際上是通過您的跟蹤代碼，就可以很清楚地看到爲什麼它會返回一個不正確的結果。我在下面標明如果沒有樹的第一級的孩子的標籤匹配的代碼路徑（假設左/中/右都是非空）：

public TreeNode getNodeReference(String label){ 

    if(left!=null){ // 1: left is not null 
    if(check(left,label)==true) // 2: no match, proceed to 3 
     return left; 
    left.getNodeReference(label); // 3: called, but why? no side effect, no return. 
    } 

    if(middle!=null){ // 4 
    if(check(middle,label)==true) // 5 
     return middle; 
    middle.getNodeReference(label); // 6 
    } 

    if(right!=null) { // 7 
    if(check(right,label)==true) // 8 
     return right; 
    right.getNodeReference(label); // 9 
    } 

    return null; // 10: and finally we're here and we return null 
}

從本質上講，你叫孩子。 getNodeReference（標籤），但這就是你所做的一切。你叫它。然後丟棄返回的值並繼續執行，因此，您的搜索實際上不會超出您最初稱爲getNodeReference的節點的第一級。

所以對於初學者來說，這個一般模式是你想要什麼：

if (child != null) { 
    if (check(child, label)) 
     return child; // match found 
    TreeNode childResult = child.getNodeReference(label); 
    if (childResult != null) 
     return childResult; // match found deeper in tree; this is what you did not do. 
}

這就是說，這裏是一個更短的實施（請記住，這是不準確像你有什麼，您的實現也跳過檢查），其getNodeReference首次被實際節點：

public TreeNode getNodeReference (String label) { 

    if (check(this, label)) 
     return this; 

    TreeNode childResult = null; 
    if (left != null) 
     childResult = left.getNodeReference(label); 
    if (childResult == null && middle != null) 
     childResult = middle.getNodeReference(label); 
    if (childResult == null && right != null) 
     childResult = right.getNodeReference(label); 

    return childResult; 

}

在一般情況下，你應該坐下來，看看你的代碼很難看，並且一次通過一行一步。通常，當你這樣做時，這樣的問題變得清晰。

希望有所幫助。

來源

2013-08-06 03:13:39

感謝您的回覆，它完美地解決了我的問題！順便問一下，是否有任何有用的信息或網站供學習遞歸？我發現它總是很難理解遞歸程序如何工作 – wah725

嗯;好問題。我認爲它只是帶有經驗。在SML年前的大學課程之後，我對模糊的回憶有着模糊的記憶 - 也許如果你對更高概念和抽象的東西感興趣，你可能想研究一個函數式語言，如ML，Haskell或Lisp。對於像Java這樣的聲明性語言，我在粗略的Google搜索中發現了這一點：http://erwnerve.tripod.com/prog/recursion/index.htm - 可能值得一試。考慮分形線條，數學歸納等。 –

除了有趣的話題之外，許多（所有？）程序都可以簡化爲一個有限狀態機，它可以很容易地遞歸實現。這是諸如http://research.microsoft.com/en-us/um/people/tball/papers/xmasgift/之類的程序背後的理論（它們很有趣）。 –

問題是：你沒有對內部調用的返回值做任何事情。

對於爲例：

左不爲空
檢查返回假
呼叫getNodeReference與標籤
左邊是不是空
檢查返回真
（返程真正的第一個電話，但你沒有什麼可以趕上它）
中間不爲空
檢查...
...

X.返回NULL;

BOOM！

來源

2013-08-06 03:13:48 Boubou

不能停止遞歸java

回答

相關問題