序言遞歸長度計數

這可能是一個簡單/基本的問題，但我有麻煩抓住邏輯。序言遞歸長度計數

我想使用遞歸來計算列表的長度。想象一下，對於這個問題有一個列表[a，b，c，d]。

我們有一個基本的子句和遞歸子句，如下所示。基本條款總是處理最基本的問題，在這種情況下是一個空的列表。遞歸子句試圖解決列表中大小爲N-1的問題。

listLength([],0). 

listLength([Head|Tail], Count):- 
    listLength(Tail, PartialCount), 
    Count is PartialCount+1.

現在，我的問題是：

讓我們來看看這段代碼：

listLength(Tail, PartialCount)

程序將繼續運行，直至尾是空的，那麼它會通過到listLength([],0). 其中PartialCount變爲等於0. 然後，程序繼續到Count is PartialCount+1.並且Count變成等於1.

然後程序開始回溯到其他「未解決」的長度。首先它以[d]開頭，因爲這是它試圖解決的最後一個元素，現在PartialCount變成1，這就是我不明白的地方。 PartialCount如何突然變爲「1」，這使Count之後等於2，因爲在程序中沒有重新定義PartialCount的指示。

該程序還回溯到[c，d]，這使得部分計數等於2，等等。

有人可以解釋這是怎麼發生的？據我所知，listLength([],0]示例中的PartialCount設置爲「0」，但我不知道它的值如何更新？我看到Count得到更新，但不PartialCount

來源

2017-11-18 aze45sq6d

有一個在每次遞歸調用單獨PartialCount。這就像局部變量與全球一樣。局部變量掩碼具有相同名稱的全局變量。最深嵌套中的局部變量掩蓋了它之外的變量。

加法：這是發生了什麼：

Call [a,b,c,d] 
    Call [b,c,d] 
    Call [c,d] 
     Call [d] 
     Call [] 
     Success (first clause): Count = 0, no ParticalCount 
     Success (2nd clause): PartialCount = 0, Count = 1 
    Success (2nd clause): PartialCount = 1, Count = 2 
    Success (2nd clause): PartialCount = 2, Count = 3 
Success (2nd clause): PartialCount = 3, Count = 4

來源

2017-11-18 12:39:17

如果我理解正確，回溯的時候它可以追溯到listLength（尾，PartialCount），對不對？或者它一直回到listLength（[Head | Tail]，Count） – aze45sq6d

其實根本沒有回溯。代碼是確定性的。只有一個子句可以匹配，即參數1中的空列表或非空列表。將在答案中加上解釋。 –

我真的試圖去理解它，但我仍然不理解「PartialCount」如何不斷更新。我沒有看到任何值添加到PartialCount。 – aze45sq6d

序言遞歸長度計數

回答

相關問題