Question

Hi. I'm working on Problem Set 3.0 (for the fall section). I'm stuck on problem 1 (recursive program to count the number of 'key' strings in a 'target' string). Has anyone found a solution for this? The best I can think of is this...

def MR(target, key):
p = 0
L = len(target)
if L == 1:
print p
return
if target[(L-2):L] == key:
p = p+1
MR(target[0:(L-1)], key)

Which should work except for that my variable p keeps resetting. (Is this the kind of question 'open sudy' is for?)

Answer 1

def countOccurence( target, key ):
foo = target.find( key )
if( foo < 0 ):
return 0
else:
return countOccurence( target[ foo: ], key ) + 1

# This code isn't tested.

Answer 2

Hm, I took your use of the target.find command. But I think you just needed a way to increment your 'target search' - you're searching from the same place every time. This is what I finally came up with... its pretty similar.

def MatchesRecursive(target, key):

p = 0 #number of slices
s = target.find(key, 0)

if s != -1:
p = p+1
p = p + MatchesRecursive(target[s+1:], key)
return p
print target, key, p, s

Maybe I could rewrite it so it doesn't have that p variable and just incremented the number of hits by adding one, like you did?

Answer 3

It should have been:

return countOccurence( target[ foo + 1 : ], key ) + 1

Told you it wasn't tested.