<div class="gmail_quote">On Fri, Aug 20, 2010 at 8:12 AM, Baba <span dir="ltr"><<a href="mailto:raoulbia@gmail.com">raoulbia@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Level: Beginner<br>
<br>
exercise source:<br>
<a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset3.pdf" target="_blank">http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset3.pdf</a><br>

<br>
I am looking at the first problem in the above assignment. The<br>
assignemnt deals, amongst others, with the ideas of iterative vs.<br>
recursive coding approaches and i was wondering what are the<br>
advantages of each and how to best chose between both options?<br>
<br></blockquote><div><br>With Python, I'd avoid using recursions unless it is absolutely needed / much simpler than iteration and depth is known in advance, and not exceeds the limit.<br>Reason is that Python does not optimize recursion calls, and even tail recursions get own stack frame on each call. <br>
It is more expensive than iteration and risks to exceed max recursion depth. <br><br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
part 2 recursive approach:<br>
<br>
<br>
def countSubStringMatchRecursive(target,key):<br>
    counter=0<br>
    fsi=0     #fsi=find string index<br>
    if len(key)==len(target):       #base case<br>
      if key==target:<br>
           counter+=1<br>
    elif len(key)<len(target):<br>
        while fsi<len(target):<br>
            fsi=target.find(key,fsi)<br>
            if fsi!=-1:<br>
               counter+=1<br>
            else:<br>
                break<br>
            fsi=fsi+1<br>
    else:<br>
        print 'key is longer than target...'<br>
<br>
    print '%s is %d times in the target string' %(key,counter)<br>
<br>
countSubStringMatchRecursive("atgacatgcacaagtatgcat","atgacatgcacaagtatgcatatgc")<br clear="all"></blockquote></div><br>Maybe I'm missing something, but this one seems to be iterative too. Recursive is one which calls itself, like<br>
<br>def countSubString(haystack, needle):<br>     def checkMatch(haystack, needle):<br>          if not needle:<br>              return True<br>          elif not haystack:<br>              return False<br>          elif haystack[0] == needle[0]:<br>
              return checkMatch(haystack[1:], needle[1:])<br>          else:<br>              return False<br>     return len(filter(bool, map(lambda i: checkMatch(haystack[i:], needle), range(len(haystack)))))<br>          <br>
Where checkMatch would be called recursively to match needle over particular part of haystack.<br><br>-- <br>With best regards,<br>Daniel Kluev<br><br>