Iterative vs. Recursive coding

[Daniel Kluev]

On Fri, Aug 20, 2010 at 8:12 AM, Baba <raoulbia at gmail.com> 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?
>
>
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.
Reason is that Python does not optimize recursion calls, and even tail
recursions get own stack frame on each call.
It is more expensive than iteration and risks to exceed max recursion depth.


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")
>

Maybe I'm missing something, but this one seems to be iterative too.
Recursive is one which calls itself, like

def countSubString(haystack, needle):
     def checkMatch(haystack, needle):
          if not needle:
              return True
          elif not haystack:
              return False
          elif haystack[0] == needle[0]:
              return checkMatch(haystack[1:], needle[1:])
          else:
              return False
     return len(filter(bool, map(lambda i: checkMatch(haystack[i:], needle),
range(len(haystack)))))

Where checkMatch would be called recursively to match needle over particular
part of haystack.

-- 
With best regards,
Daniel Kluev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20100820/239a1a3c/attachment-0001.html>