Baba wrote:
Level: Beginner
exercise source:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset3.pdf
I am looking at the first problem in the above assignment. The
assignemnt deals, amongst others, with the ideas of iterative vs.
recursive coding approaches and i was wondering what are the
advantages of each and how to best chose between both options?
I had a go at the first part of the exercise and it seems that i can
handle it. However i think my Recursive version can be improved. By
the way, is my code actually proper recursive code?
part 1 iterative approach:
from string import *
def countSubStringMatch(target,key):
counter=0
fsi=0 #fsi=find string index
while fsi<len(target):
fsi=target.find(key,fsi)
#print fsi
if fsi!=-1:
counter+=1
else:
break
fsi=fsi+1
print '%s is %d times in the target string' %(key,counter)
countSubStringMatch("atgacatgcacaagtatgcat","zzz")
part 2 recursive approach:
def countSubStringMatchRecursive(target,key):
counter=0
fsi=0 #fsi=find string index
if len(key)==len(target): #base case
if key==target:
counter+=1
elif len(key)<len(target):
while fsi<len(target):
fsi=target.find(key,fsi)
if fsi!=-1:
counter+=1
else:
break
fsi=fsi+1
else:
print 'key is longer than target...'
print '%s is %d times in the target string' %(key,counter)
countSubStringMatchRecursive("atgacatgcacaagtatgcat","atgacatgcacaagtatgcatatgc")
tnx
Baba
A function that doesn't call itself (directly or indirectly) isn't
recursive. So you don't have any recursion here.
An example of recursion might be where your function simply compares the
key to the beginning of the target, then calls itself with a substring
of the target ( target[1:] ) Don't forget to return 0 if the target is
smaller than the key.
And take the print out of the recursive function. Write a separate
function that does that, after calling the worker function.
DaveA
--
http://mail.python.org/mailman/listinfo/python-list
