Iterative vs. Recursive coding

MRAB python at mrabarnett.plus.com
Thu Aug 19 23:45:53 CEST 2010


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")
> 
'countSubStringMatchRecursive' isn't recursive at all.



More information about the Python-list mailing list