How to keep count in a recursive function?

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,k开发者_如何学运维ey)
    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

---

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)

---

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)

---

Just a side note: all solutions presented (from the original Q to all the As) are solving a problem that's different than the specifically stated one (I imagine that's a bug in the specific problem statement, but, worth fixing if so;-). Consider:

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

the first expression is counting the non-overlapping occurrences of 'ana' in 'banana'; the second one is counting all occurrences -- there are two occurrences in all, at indices 1 and 3 in 'banana', and they overlap. So given the problem statement, and I quote:

find the no. of instances of a substring in the parent string.

without any mention of "non-overlapping", it seems that overlapping occurrences should be counted. Of course, that's easy to fix, once noticed -- you just have to advance by 1 each time, instead of advancing by len(key) which leads you to skip overlapping occurrences.

So, for example:

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')

prints 2, counting both (overlapping) occurrences.

---

Here's something similar to Greg Hewgill's answer. However, instead we pass along the current count each time we call the function, and then return the count when there are no more matches to be made. While I suspect it makes no difference in Python, in languages that implement tail-call recursion, this allows each successive call to do_count to be optimised away on the call stack. This means that each call to do_count doesn't cause the call stack to grow.

def count_sub_strings(target, key):
    def do_count(target, key, count):
        index = target.find(key)
        if index >= 0:
            target = target[index + len(key):]
            return do_count(target, key, count + 1)
        else:
            return count
    return "No. of instances of %s in %s is %s" % (key, target, do_count(target, key, 0))

---

I'm doing this course on OpenCourseware, it's great. Anyways, this is what I did. I took inspiration from adamse above.

def countSubStringMatchRecursive(target, key, counter = 0):
    if find(target,key) == 0:
        countSubStringMatchRecursive(target[1:], key, counter + 1)
    elif find(target,key) > 0:
        countSubStringMatchRecursive(target[1:], key, counter)
    elif find(target,key) == -1:
        print counter

---

Taking into account overlapping occurrences and maintaining the original definition from MIT this is the simpler and more compact code that I can get.

code:

from string import *
def countSubStringMatchRecursive(target, key):
    index = find(target, key)
    if index > -1:
        return countSubStringMatchRecursive(target[index + 1:], key) + 1
    return 0


def test(target, key):
    instances = countSubStringMatchRecursive(target, key)
    if instances == 0:
        print "No instance of %r in %r" % (key, target)
    else:
        print "Number of instances of %r in %r: %d" % (key, target, instances)

test("atgacatgcacaagtatgcat","ggcc")
test("atgacatgcacaagtatgcat","atgc")
test("banana", "ana")

output:

No instance of 'ggcc' in 'atgacatgcacaagtatgcat'

Number of instances of 'atgc' in 'atgacatgcacaagtatgcat': 2

Number of instances of 'ana' in 'banana': 2

---

def countSubStringMatchRecursive(target, key):
    index = string.find(target, key)
    if index == -1:
        return 0
    else:
        return 1 + countSubStringMatchRecursive(target[index + len(key):], key)

---

How about this?

def count_it(target, key):
    index = target.find(key)
    if index >= 0:
        return 1 + count_it(target[index+len(key):], key)
    else:
        return 0


print count_it("aaa bbb aaa ccc aaa", "aaa")

Output:

3

---

Not untested ...

code:

def countSubStringMatchRecursive(target, key, count=0):
    #### index = find(target, key) # HUH?
    index = target.find(key)
    if index >= 0:
        count += 1
        target = target[index+len(key):]
        count = countSubStringMatchRecursive(target, key, count)
    return count

for test in ['', 'bar', 'foo', 'foofoo', 'foo foo foo fo']:
   print countSubStringMatchRecursive(test, 'foo'), test.count(key), repr(test)

output:

0 0 ''
0 0 'bar'
1 1 'foo'
2 2 'foofoo'
3 3 'foo foo foo fo'

I'm presuming that this is just amusement or homework ... recursive function must be slower than corresponding Python iterative solution, which will be naturally slower than using target.count(key) ... so I haven't bothered with fixing all the problems your version had ... but do read PEP-008 :-)

Comments on string module

You commented that you had omitted from string import find. What version of Python are you using? What is the last update date on the book or tutorial that you are using?

From the start of the string module (it will be on your computer as <your Python install directory>/Lib/string.py; I'm quoting from the 2.6 version):

"""A collection of string operations (most are no longer used).

Warning: most of the code you see here isn't normally used nowadays. Beginning with Python 1.6, many of these functions are implemented as methods on the standard string object. They used to be implemented by a built-in module called strop, but strop is now obsolete itself.

etc """

and here is that file's code for the find function (stripped of comments):

def find(s, *args):
    return s.find(*args)

so using string.find(target, key) instead of target.find(key) is a waste.

---

I would suggest to use singleton class pattern for tracking the counter values in recursive function.

Via simple terms, singleton class pattern will create only one instance at runtime, and it will restrict to create more than one instances for a class.(Example for singleton class in realtime: logging services, database connection services, filesystem in operating system)

Here am including the counter code for recursive function using singleton class method:

class Singleton(type):
    _instances = {}
    def __call__(cls, *args, **kwargs):
        if cls not in cls._instances:
            cls._instances[cls] = super(Singleton, cls).__call__(*args, **kwargs)
        return cls._instances[cls]
        
class CounterSingleton(object):
    __metaclass__ = Singleton


    def __init__(self):
        self.counter = 0
        self.data = []

    def update(self):
        self.counter += 1
    
    def update_log(self, val):
        self.data.append((val, self.counter))

    def get(self):
        return self.counter


count_single = CounterSingleton()



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

reference: https://en.wikipedia.org/wiki/Singleton_pattern

---

Another way could be to have a third optional parameter on the countSubStringMatchRecursive function called count that is originally set to 0. That way you could keep track of the count. This would expose the count variable to the outside world which might not be desirable, but since it's no worse than your global variable I don't think it would be a problem in your case.

You would also have to change the code to make the last recursive call be the call that gives the return statement to the outside world. See this example (untested):

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

Edit: I realised that you would need a fourth parameter to be able to keep the original string traveling along the recursion. This is probably a less than optimal solution and I would recommend using Greg Hewgill's solution. It has a clean separation between the interactions with the outside and the "business logic", making the code more reusable!

---

steps = 0
def addPersistence(number, steps):
    steps += 1
    if len(str(number))==1:
        print(str(number) + "\nDone---------------------------------------------------")
        print("TOTAL STEPS " + str(steps-1))

    digits = [int(i) for i in str(number)]

    result = 0
    for j in digits:
        result += j


    if len(str(number)) != 1:
        print(number)
        addPersistence(result, steps)

This is a example copied from one of my projects. This function is to determine to addition persistence of a number (which is adding the digits of a number and repeating it until the number gets to 1) but it surely can be reusable and you can use your function like this (This is Python 3 code, if you want to change it to Python 2, it will still work):

count=0
def countSubStringMatchRecursive(target,key,count):
    index=find(target,key)
    targetstring=target
    if index>=0:
        count+=1
        target=target[index+len(key):]
        countSubStringMatchRecursive(target,key,count)
    else :
        pass
    print("STEPS: "+str(count))

You might notice my code and that code are a little bit different. Why? The answer is that the number of steps it takes for a number to get to 1 using that function is that the last call isn't included in my function because it's a duplication of the call before that.

---

This answer is so convenient, I have to share it in this post also:

https://stackoverflow.com/a/41203348/6146879

(Use of assignment to a function)