序言递归长度计数

这可能是一个简单/基本的问题，但我有麻烦抓住逻辑。序言递归长度计数

我想使用递归来计算列表的长度。想象一下，对于这个问题有一个列表[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

序言递归长度计数

回答

相关问题