Iterative vs. Recursive coding

Baba raoulbia at gmail.com
Sat Aug 21 01:22:44 CEST 2010


Hi Martin

Thanks for your post. This basic but fundamental computation is a
great example when trying to understand the concept of recursion for
the first time.

Also thanks to John for the stackoverflow link where i found a very
good summarised definition completing some of the posts left here.

For future readers of this post who want to learn to programm (just
like myself) let me re-state the basics i have learned now:

- a procedure is said to be recursive when it contains a statement
that calls itself
- there must be a condition where the recursion has to stop otherwise
the routine will continue to call itself infinitely.
  This is called the Base Case
- every time the procedure calls itself the memory gradually fills up
with the copies until the whole thing winds down again
  as the "return" statements start being executed.
- the above point means that a recursive approach is expensive on
resources so in the practical world it should be avoided.
  (Thanks John for giving me a real life example where recursion is
recommended)

For the purposes of learning programming i think it's a must to
understand Recursion so thanks all for your help!

Ok so now i hope you all agree that my code is also correct :)

def r_countSubStringMatch(target,key):
    counter=0
    if len(key)<len(target):
      fsi=target.find(key)
      if fsi!=-1:  # BASE CASE
          counter=1+r_countSubStringMatch(target[fsi+1:],key)
          return counter
      else:
          return counter
    elif len(key)==len(target):
        if key==target:
            counter+=1
            return counter
    else:
        return counter
    return counter

print r_countSubStringMatch("atgacatgcacaagtatgcat","atgc")


tnx
Baba



More information about the Python-list mailing list