使用递归计算列表中一个数字的出现次数

Question

我正在处理的任务是：

给定一个int数组，递归计算数组中出现值为11的次数。我们使用的约定是仅考虑从给定索引开始的数组部分。通过这种方式，递归调用可以传递index+1来遍历整个数组。

我需要使用递归来完成此任务。虽然我在这方面相对较新，但我已经基本实现了它。 以下是我的代码：

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”数组！

那么这种方法可接受吗？你会用相同的方式做吗？

提前感谢。

- RRR

---

这几乎肯定是基于个人意见的，而且由于它是工作代码，也许更适合于代码审查。 话虽如此，数组不是递归数据类型（与单链表相反），因此考虑到数据类型，这似乎是一个非常自然的解决方案。 此外，它是尾递归的，因此可以编译成循环，这是很好的。 - Joshua Taylor

在提问之前尝试解决问题会得到加分。我修改了你的标题以反映手头的问题。 - timgeb

没问题，感谢你的输入 Joshua。 - RRR

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。因此，将布尔值（或布尔值和整数）相加会导致将布尔值解释为整数。

然后，在array11()的最外层调用上使用print。

- Martijn Pieters

---

但是 OP 的代码是尾递归的 :| - Hunter McMillen

这个加法没有链式效果吗？array11([11,2,3], 0) 会产生 1 + array11([11,2,3], 1) -> 1 + 0 + array11([11,2,3], 2) -> 1 + 0 + 0 + array11([11,2,3], 3) -> 1 + 0 + 0 + 0 = 1，是对的吗？ - Hunter McMillen

+1 但是你可能想在布尔表达式周围加上括号，以使你正在做什么更清晰一些。 - scohe001

@Josh：已完成，还添加了关于arr[index] == 11可相加的说明。 - Martijn Pieters

@HunterMcMillen：目前没有Python实现它。Python的创造者已经明确表示这不是一个好主意（http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html）。 - Martijn Pieters

Answer 2

这是完全可接受的方法，虽然不是执行尾递归最干净的方式。你正在使用一个累加器来跟踪计数，这使得你能够拥有更高效的尾递归（一种更有效的递归类型）。

然而，正如BlackVegetable指出的那样，Python不允许你享受尾递归的好处，但理解使用累加器与Martijn Pieter答案中的自顶向下方法之间的差异仍然值得注意。

- C.B.

---

使用累加器并不特别“不干净”；更干净的方法可能是像这样调用array11(arr,index,cnt+1,num+1)，而不是修改cnt和num然后再进行调用。 - Joshua Taylor

@JoshuaTaylor 当然，我指的更多是代码本身。他可以以不同的方式使用累加器。现在你对OP的问题的评论确实很正确 :) - C.B.

据我所知，Python 中没有对尾递归调用进行优化。 - BlackVegetable

@BlackVegetable 很好的观点。 - C.B.

Answer 3

在Python 3中，它可以如此简洁：

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中的递归，因此假设性能不是因素。

- Thijs van Dien