Iterative vs. Recursive coding

Baba raoulbia at gmail.com
Thu Aug 19 23:12:44 CEST 2010


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



More information about the Python-list mailing list