MJ49 MJ49 - 7 days ago 5
Python Question

Recursive Python Simple Function

I'm doing the MIT Intro to CS class to learn python and am stuck on a problem set involving recursive programming(calling a function within itself). The goal is to find a number of occurrences for a given target string. I have the following code and from my logic it seems like it should but I can't figure out why it doesn't! Any help is much appreciated. Thanks.

def countSubStringMatchRecursive(target,key):
answers = []
match = target.find(key)

if match != -1:
answers.append(match)
next_target = target[match+1:]
countSubStringMatchRecursive(next_target,key)

return len(answers)


So for given arguments:

target1 = 'mjzzmjzzmj'
key1 = 'zz'

print(countSubStringMatchRecursive(target1, key1))


I get 1 instead of the correct answer of two.

This is on Python3 btw.

Answer

Since you don't need the answers.. you don't need the answers; just a count.

from __future__ import print_function


def countSubStringMatchRecursive(target, key):
    match = target.find(key)

    if match != -1:
        next_target = target[match+1:]
        return 1 + countSubStringMatchRecursive(next_target, key)
    else:
        return 0


print(countSubStringMatchRecursive('asd asd asd', 'sd'))  # 3
print(countSubStringMatchRecursive('ababa', 'ab'))  # 2

This does count overlapping matches; let me know if that's not what you want.