Iterative vs. Recursive coding

[Dave Angel]

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