CODEWITHSUNDEEP
python
BAbabo
BAbabo

Reputation: 11

How to make recursive function that counts the number of occurences in a string in python

I tried this to count the number of occurences of the target in a string in a recursive way, but I don't think where len(target) > 1 is a recursive way. I can't really think of other way to do this in a recursive way. I am doing this without using any string methods except indexing and slicing. Please give some help.

target can be a single character or a substring.

For example, if s = 'aaaaabb' and target = 'aa', i want the output to be 4.

def count(s, target):
    if s == '':
        return 0
    if len(target) > len(s):
        return 0

    if len(target) <= 1:
        if s[0] == target:
            return 1 + count(s[1:], target)
        else:
            return 0 + count(s[1:], target)

    if len(target) > 1:
        count = 0
        for x in range(len(s) - len(target) + 1):
            if s[x:x+len(target)] == target:
                count += 1
        return count

Upvotes: 0

Views: 162

Answers (1)

j1-lee
j1-lee

Reputation: 13939

Try:

def count_substring(s, target):
    if not s:
        return 0
    return (s[:len(target)] == target) + count_substring(s[1:], target)

print(count_substring('aaaaabb', 'aa')) # 4

The idea is that at each recursion, the function only cares about the left-most substring, to compare with target. You can think of it as a slight modification of your len(target) <= 1 case.

Upvotes: 1

Related Questions