遞歸函數丟失返回語句

Question

我是新來遞歸，我不明白爲什麼這個函數不會編譯。它顯然缺少一個返回聲明。從測試看來，似乎我的回報聲明不會返回？

// recursive search method 
public BinaryTree<T> recursiveSearch(BinaryTree<T> t, T key) { 
    if (key.compareTo(t.getData()) < 0) { 
     if (t.getLeft() != null) { 
      recursiveSearch(t.getLeft(), key); 
     } else { 
      return null; 
     } 
    } else if (key.compareTo(t.getData()) > 0) { 
     if (t.getRight() != null) { 
      recursiveSearch(t.getRight(), key); 
     } else { 
      return null; 
     } 
    } else if (key.compareTo(t.getData()) == 0) { // key is found 
     return t; 
    } else { // not in binary tree 
     return null; 
    } 
} 

Answer 1

問題出在遞歸調用的if分支內。

當您的代碼到達您的任何else分支時，您的代碼將會正常運行，因爲它們都有return null。但是，如果代碼採用if分支之一，則控制將達到方法的結尾，而不會觸及return。解決方法是簡單的 - 添加缺少的return S：

return recursiveSearch(t.getRight(), key); 

Answer 2

是的，它缺少了遞歸語句return語句。

public BinaryTree<T> recursiveSearch(BinaryTree<T> t, T key) 
{ 
    if (key.compareTo(t.getData())<0){ 
     if (t.getLeft() != null) { 
      recursiveSearch(t.getLeft(), key); // This case doesn't return anything 
     } else { return null;} 
    } else if (key.compareTo(t.getData())>0) { 
     if (t.getRight() != null) { 
      recursiveSearch(t.getRight(), key); // This case doesn't return anything 
     } else {return null;} 
    } else if (key.compareTo(t.getData())==0){ // key is found 
     return t; 
    } else { 
     //not in binary tree 
     return null; 
    } 
} 

我不知道你的程序邏輯，但如果我有猜測，你可能要添加一個return語句到遞歸調用。像這樣，

return recursiveSearch(t.getLeft(), key); 

和

return recursiveSearch(t.getRight(), key);