以遞歸方式返回鏈表中的元素數

我在名爲ImageNode的類中有一個名爲Image的類，該類傳遞了頭（，這個 - 鏈表的起點）。我以爲我的代碼會遞歸地遍歷每個節點，增加計數，然後當它在最後返回計數，不幸的是不。我哪裏錯了？以遞歸方式返回鏈表中的元素數

private int countRec() { 
    int count = 1; 
    ImageNode node = this; 

    if (node.next != null){ 
     node = node.next; 
     count++; 
     countRec(); 
    } 

    return count; 
}

來源

2014-09-19 Dan_ENZ

'int count = 1;'你總是將計數設置爲1，遞增並返回它。 – TheLostMind 2014-09-19 06:16:29

計數不應該是您的方法的局部變量 – zerocool 2014-09-19 06:16:49

您正在通過方法調用重置計數，並且每個countRec（）方法都會將計數設置爲'1'，將節點設置爲'this'每次都會產生相同的結果 – 2014-09-19 06:18:27

你忽略的countRec()的結果 - 而你迭代遞歸調用中，擊敗目的。（你也在同一個對象上進行遞歸調用，沒有參數，也沒有狀態變化......所以不能做任何好事。）我的遞歸方法將基於以下設計：

如果下一個節點爲空，那麼列表的大小爲1
否則，大小爲1 +從下一個節點開始的大小。

所以：

private int countRec() { 
    return next == null ? 1 : 1 + next.countRec(); 
}

現在不允許長度爲0的列表，當然......你可能想單獨從節點列表的想法，在這種情況下，列表類將有類似：

public int count() { 
    return head == null ? 0 : head.countRec(); 
}

其中head值是頭節點的引用，如果有一個或null否則。

當然，這將是O（n）在時間和的空間。您可以使用迭代而不是遞歸獲得O（1）空間，並通過將列表的大小作爲實例變量保存在列表中來獲得O（1）空間，並在需要時更新它。我希望這個問題是基於教育需求而不是真正的代碼 - 在生產代碼中，您只需使用已提供的集合。

來源

2014-09-19 06:19:03

謝謝！那完美的作品，從來沒有用過？之前，有點困惑至於什麼？和：正在做 – 2014-09-19 06:24:15

@Dan_ENZ：它是條件運算符 - 它在'？'之前檢查條件，然後計算第二個參數或第三個參數。會鏈接到一些文件，但現在必須下車... – 2014-09-19 06:26:00

不用擔心會有一個看看它。謝謝您的幫助。 – 2014-09-19 06:27:55

遞歸函數的定義是根據自身定義的：即如果列表中的元素的數量等於0;否則它等於列表列表中其餘元素的計數1 + 。

上述定義的斜體部分是進行函數調用的地方。

private int countRec(ImageNode node) { if (node == null) { return 0; } else { return 1 + countRec(node); } }

來源

2014-09-19 06:24:27

遞歸函數在使用進一步調用的結果來解決他的問題（如數學上的歸納步驟）時非常有用。您的函數沒有使用countRec()調用的任何回報，並且您仍然試圖在沒有遞歸幫助的情況下解決問題。您可以使用它解決它，如：

if(node.next != null) 
{ 
    node = node.next; 
    count = countRec()+1; 
} 
return count;

當然，因爲我們講述讓你的代碼更好，你甚至不會需要使用這個node變種，只是在做：

private int countRec() { 

    if (this.next != null) 
     return (this.next.countRec())+1; 
    return 1; 
}

希望有幫助。

來源

2014-09-19 06:32:11

以遞歸方式返回鏈表中的元素數

回答

相關問題