如何在递归函数中保持计数？

Question

我写了一个递归函数，用来找出一个子字符串在父字符串中出现的次数。

我统计次数的方法是把 count 声明为全局变量，也就是在函数外面初始化。问题是，这样做只有第一次运行函数时结果是正确的，因为之后 count != 0 了。而如果我把它放在函数里面，每次递归调用的时候，它都会被重置为0。

count=0
def countSubStringMatchRecursive(target,key):
    index=find(target,key)
    global count
    targetstring=target
    if index>=0:
        count=count+1
        target=target[index+len(key):]
        countSubStringMatchRecursive(target,key)
    else :
        pass
    return "No. of instances of", key, 'in', targetstring, 'is', count

注意：我特别在找递归函数的解决方案，我有一个迭代函数是可以正常工作的。

编辑：谢谢大家，这个是作业的一部分，所以我只使用了字符串模块。

Answer 1

顺便提一下：这里提到的所有解决方案（从最初的问题到所有的回答）其实解决的是一个和原问题不太一样的问题（我想这可能是原问题描述中的一个错误，不过如果真是这样，值得修正一下；-）。考虑一下：

>>> 'banana'.count('ana')
1
>>> sum('banana'[x:x+3]=='ana' for x in range(len('banana')))
2

第一个表达式是在计算'banana'中不重叠的'ana'出现次数；而第二个表达式是在计算所有的出现次数——总共有两个出现，分别在'banana'的索引1和3的位置，它们是重叠的。所以根据问题描述，我引用一下：

找出一个子字符串在父字符串中出现的次数。

没有提到"不重叠"，所以重叠的出现次数应该被计算在内。当然，一旦注意到这个问题，修正起来很简单——你只需要每次向前移动1，而不是移动len(key)，这样就不会跳过重叠的出现。

所以，比如说：

import string

def countit(target, key, startfrom=0):
    where = string.find(target, key, startfrom)
    if where < 0: return 0
    return 1 + countit(target, key, where+1)

print countit('banana', 'ana')

会打印2，计算了两个（重叠的）出现次数。

Answer 2

你的递归函数性能是O(n^2)，因为每次找到匹配时，它都会复制字符串中剩下的内容。这比迭代的方法O(n)要慢，而且这种慢是没必要的。

你可以很容易地重写这个函数，让它更快，同时简化代码，还可以通过传递一个起始索引作为可选参数来扩展它的功能：

def countSubStringMatchRecursive(target, key, start_index = 0):
    index = target.find(key, start_index)
    if index >= 0:
        return countSubStringMatchRecursive(target, key, index + len(key)) + 1
    return 0

target_string = 'an apple and a banana'
key = 'an'
count = countSubStringMatchRecursive(target_string,  key)
print "Number of instances of %r in %r is %d" % (key, target_string, count)

输出：

Number of instances of 'an' in 'an apple and a banana' is 4

更新：如果你真的想使用字符串模块的find函数，只需改一行代码就可以做到：

index = find(target, key, start_index)

Answer 3

修改你的代码有一种方法，就是使用一个本地函数，具体可以这样写：

def countSubStringMatchRecursive(target,key):
    def countit(target,key,count):
        index=find(target,key)
        if index>=0:
            target=target[index+len(key):]
            count += countit(target,key,count) + 1
        return count
    return "No. of instances of", key, 'in', target, 'is', countit(target,key,0)