Iterative vs. Recursive coding

John Nagle nagle at animats.com
Fri Aug 20 06:53:55 CEST 2010


On 8/19/2010 2:41 PM, Thomas Jollans wrote:
> On Thursday 19 August 2010, it occurred to Baba to exclaim:

> This is not recursive. In fact, it's exactly the same approach as
> the first one, plus a bit of an if statement.

    Right.  The original poster seems to be getting their ideas
from

"http://stackoverflow.com/questions/2308696/substring-recursive-algorithm-not-working"

which is a rather confused article, or

http://talkbinary.com/programming/c/c-recursion-palindrome/

which really has a recursive, although inefficient, example.

If you're really interested in this area, read
up on the Boyer-Moore Fast String Search Algorithm, which is
the fast way to do this for long strings.

For Python, a quick solution is

def countSubStringMatch(target, key) :
     esckey = re.sub(r'(\W)',r'\\\1',key) # put \ escapes into key
     cnt = len(re.findall(esckey, target)) # find all key and count
     print('%s is %d times in the target string' %(key,cnt))

 >>> countSubStringMatch("atgacatgcacaagtatgcat","ca")
ca is 4 times in the target string

Enjoy.

				John Nagle



More information about the Python-list mailing list