计算数字在列表中的次数（使用递归）

Question

我的任务是：

Given an array of ints, compute recursively the number of times that the value 11 appears in the array. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array.

我需要递归地这样做。我对这方面还不太熟悉，但从技术上讲我做到了。 我有以下几点：

def array11(arr, index, cnt=0, num=0):
    if(cnt==len(arr)-index):
        print("yay!!! number 11 appears %d times"%num)
        return
    elif(arr[index:][cnt]==11): 
        num+=1
        cnt+=1
        array11(arr,index,cnt,num)
    else: 
        cnt+=1
        array11(arr,index,cnt,num)

但我觉得出于某种原因，我用了一种廉价的方法，用默认值添加了“cnt”和“num”参数。我只是不知道如何在没有计数器的情况下通过“arr”数组！！你知道吗

所以这是可以接受的？你会用同样的方法吗？你知道吗

提前谢谢

Answer 1

您通常返回总计数：

def array11(arr, index):
    if index == len(arr):
        return 0
    return (arr[index] == 11) + array11(arr, index + 1)

我在这里使用了一个小Python技巧，bool是int的子类，True等于1。因此，将布尔值（或布尔值和整数）相加会导致布尔值被解释为整数。你知道吗

您可以使用print，然后在对array11()的最外层调用返回的任何内容上使用。你知道吗

Answer 2

在Python3中，它可以如此简洁：

arr = [11, 0, 4, 7, 2, 11, 6, 11, 12]

def count11(arr):
    if not arr:
        return 0
    first, *rest = arr
    return (1 if first == 11 else 0) + count11(rest)

count11(arr) # 3

列表切片可能不是很有效，但是因为我们讨论的是Python中的递归，所以假设性能不是一个因素。你知道吗

Answer 3

这是完全可以接受的，尽管不是执行尾部递归的最干净的方法。您所做的就是使用累加器来跟踪您的计数，这允许您使用尾部递归（更有效的递归类型）。你知道吗

然而，正如blackplageture所指出的，Python不允许您获得尾部递归的好处，但是在Martijn Pieter的回答中，理解使用累加器和自顶向下方法之间的区别是绝对值得注意的。你知道吗