How to keep count in a recursive function?

Question

I wrote a recursive function to find the number of instances of a substring in the parent string.

The way I am keeping count is by declaring/initialising count as a global variable outside the function's scope. Problem is, it'll give me correct results only the first time the function is run, because after that count != 0 to begin with. And if i have it inside the function, than each time it is called recursively, it'll be set to 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 

Note: I am looking for the solution for a recursive function specifically, I have an iterative function that does work fine.

EDIT: Thank You all, this was part of homework, so I was only using the string module

Answer 1

One way to modify your code would be to use a local function as follows:

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) 

Answer 2

Your recursive function has O(n^2) performance because it copies the remaining contents of the string each time it finds a match. This is slower than the iterative solution O(n) and unnecessarily so.

You can easily rewrite it to be faster, and at the same time simplify the code and extend its functionality by passing a start index for the search as an optional parameter to the function:

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) 

Output:

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

Update: If you really want to use the string module's find function, you can do this just by changing one line:

index = find(target, key, start_index)