I did problems 2-4 using iterative solutions, so I'd be especially interested in seeing recursive solutions for those problems.
Okay, thanks to accidentally doing the wrong problem set first, it's taken a while, but here are the recursive versions of problems 2 and 3. I don't know if I'll have time to do the fourth one. My next teaching session starts this weekend, and I'm trying to finish a short story for a writing challenge (deadline Sunday), so I'm kind jammed up.
I've tested both of these against my own iterative functions as well as jetamors's, and they do yield the same results.
# Problem 2: recursive
def subStringMatchExactR( target, key ):
if key:
if target.rfind(key) == -1:
return ()
else:
offset = target.find(key) + 1
return (target.rfind(key),) + subStringMatchExactR(target[:target.rfind(key)],key)
else:
# A little something he didn't mention: In the next step, if the key
# is a single letter and key1 or key2 is empty, n+m+1 at the last n
# overruns the last index, even though the last index is an
# acceptable value. Therefore, we have to add an extra index when key
# is empty.
return range(0, len(target)+1 )
def constrainedMatchPairR( firstMatch, secondMatch, length ):
if not firstMatch:
return ()
else:
tryK = firstMatch[-1] + length + 1
if tryK in secondMatch:
return (firstMatch[-1],) + constrainedMatchPairR(firstMatch[:-1], secondMatch, length)
else:
return constrainedMatchPairR(firstMatch[:-1], secondMatch, length)
no subject
Okay, thanks to accidentally doing the wrong problem set first, it's taken a while, but here are the recursive versions of problems 2 and 3. I don't know if I'll have time to do the fourth one. My next teaching session starts this weekend, and I'm trying to finish a short story for a writing challenge (deadline Sunday), so I'm kind jammed up.
I've tested both of these against my own iterative functions as well as![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
jetamors's, and they do yield the same results.
# Problem 2: recursive def subStringMatchExactR( target, key ): if key: if target.rfind(key) == -1: return () else: offset = target.find(key) + 1 return (target.rfind(key),) + subStringMatchExactR(target[:target.rfind(key)],key) else: # A little something he didn't mention: In the next step, if the key # is a single letter and key1 or key2 is empty, n+m+1 at the last n # overruns the last index, even though the last index is an # acceptable value. Therefore, we have to add an extra index when key # is empty. return range(0, len(target)+1 ) def constrainedMatchPairR( firstMatch, secondMatch, length ): if not firstMatch: return () else: tryK = firstMatch[-1] + length + 1 if tryK in secondMatch: return (firstMatch[-1],) + constrainedMatchPairR(firstMatch[:-1], secondMatch, length) else: return constrainedMatchPairR(firstMatch[:-1], secondMatch, length)