Iterative vs. Recursive coding

Discussion in 'Python' started by Baba, Aug 19, 2010.

  1. Baba

    Baba Guest

    Level: Beginner

    exercise source:
    http://ocw.mit.edu/courses/electric...d-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
     
    Baba, Aug 19, 2010
    #1
    1. Advertising

  2. On Thursday 19 August 2010, it occurred to Baba to exclaim:
    > 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","atgacatgcacaagtatgcat
    > atgc")


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

    Take another good look at the definition of "recursion" I'm sure you were
    given.
    To sum it up:

    "iterate": use a loop. and again. and again. and again. and again. and aga....

    "recurse": consider. recurse.

    This is another good one:

    http://mytechquest.com/blog/wp-content/uploads/2010/05/From-a-Programming-Book.jpg

    - Thomas

    PS: If you think you're thinking, then you're really only thinking that
    you're thinking. Or are you?
     
    Thomas Jollans, Aug 19, 2010
    #2
    1. Advertising

  3. Baba

    MRAB Guest

    Baba wrote:
    > Level: Beginner
    >
    > exercise source:
    > http://ocw.mit.edu/courses/electric...d-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.
     
    MRAB, Aug 19, 2010
    #3
  4. On Thu, 19 Aug 2010 14:12:44 -0700, 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?
    >

    No, it isn't.

    By way of a hint, here are two versions of the classic example of
    recursion: calculating factorials. Recursion can be quite a trick to get
    your mind round at first, so compare the two and follow through their
    operation step by step...

    -------------------------------------------------

    def i_factorial(n):
    "Iterative factorial calculation"
    f = 1;
    for n in range(1, n+1):
    f = f * n
    return f

    def r_factorial(n):
    "Recursive factorial calculation"
    if (n > 1):
    return n * r_factorial(n - 1)
    else:
    return 1

    print i_factorial.__doc__
    for n in range(1,10):
    print "%d! = %d" % (n, i_factorial(n))

    print r_factorial.__doc__
    for n in range(1,10):
    print "%d! = %d" % (n, r_factorial(n))

    -----------------------------------------

    In case you're wondering "print i_factorial.__doc__"
    prints the docstring out of the i_factorial subroutine.
    You probably haven't covered that yet, but run it and see.


    --
    martin@ | Martin Gregorie
    gregorie. | Essex, UK
    org |
     
    Martin Gregorie, Aug 19, 2010
    #4
  5. Baba

    Dave Angel Guest

    Baba wrote:
    > Level: Beginner
    >
    > exercise source:
    > http://ocw.mit.edu/courses/electric...d-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
     
    Dave Angel, Aug 19, 2010
    #5
  6. Baba

    MRAB Guest

    MRAB, Aug 20, 2010
    #6
  7. On Thu, 19 Aug 2010 22:00:16 +0000, Martin Gregorie wrote:

    > Recursion can be quite a trick to get your mind round at first


    Really? Do people actually find the *concept* of recursion to be tricky?

    If I remember correctly, my puzzlement about recursion lasted about 15
    seconds. I remember thinking "How does the function foo know that there
    is a function foo when foo doesn't fully exist yet?", but once I accepted
    the fact that it just does it all just seemed obvious. Getting recursion
    *right* is sometimes tricky, but the idea itself isn't.

    But then, I grew up watching Doctor Who, and had no problem with the idea
    that the TARDIS could materialise *inside itself*. And from a very early
    age, I was familiar with a particular brand of Advocaat liquor where the
    label on the bottle contained a picture of a rooster holding a bottom of
    Advocaat, whose label contained a picture of a rooster holding a bottle
    of Advocaat, whose label contained a picture of a rooster holding a
    bottle, whose label ... well, you can see where that is going.


    --
    Steven
     
    Steven D'Aprano, Aug 20, 2010
    #7
  8. Baba

    John Nagle Guest

    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
     
    John Nagle, Aug 20, 2010
    #8
  9. On Thu, 19 Aug 2010 14:12:44 -0700 (PDT), Baba <>
    declaimed the following in gmane.comp.python.general:


    > 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?
    >

    Others have mentioned that it isn't anything near recursive...

    > part 1 iterative approach:
    >

    For this one, however...

    > from string import *


    Unneeded import

    > def countSubStringMatch(target,key):
    > counter=0
    > fsi=0 #fsi=find string index

    tlen = len(target) - len(key)
    # don't recompute the length of "target" each time.
    # also, a 4-character key will never be found when there are
    # less then key-length characters left to search.
    > 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")
    >


    Personally, (untested -- written off the top of my head), I'd likely
    end up with something like:

    def countMatches(key, target): #yes, reversed... look for key in target
    count = 0
    start = 0
    tlen = len(target) - len(key)
    while start < tlen:
    match = target.find(key, start)
    if match < 0: break
    count += 1
    fsi += 1
    return count
    >
    > part 2 recursive approach:
    >


    def countMatches(key, target):
    match = target.find(key)
    if match < 0: return 0
    return 1 + countMatches(key, target[match+1:])


    --
    Wulfraed Dennis Lee Bieber AF6VN
    HTTP://wlfraed.home.netcom.com/
     
    Dennis Lee Bieber, Aug 20, 2010
    #9
  10. Baba

    News123 Guest

    On 08/20/2010 02:26 AM, Steven D'Aprano wrote:
    > On Thu, 19 Aug 2010 22:00:16 +0000, Martin Gregorie wrote:
    >
    >> Recursion can be quite a trick to get your mind round at first

    >
    > Really? Do people actually find the *concept* of recursion to be tricky?

    Is this a sincere surprise or are you just boasting?
    >
    > If I remember correctly, my puzzlement about recursion lasted about 15
    > seconds. I remember thinking "How does the function foo know that there
    > is a function foo when foo doesn't fully exist yet?", but once I accepted
    > the fact that it just does it all just seemed obvious. Getting recursion
    > *right* is sometimes tricky, but the idea itself isn't.


    Well there's two things where I remember, that at least quite some
    people in our class (at least the ones who didn't do maths or
    programming in their spare time) had problems with.

    This were recursion and Mathematical induction. (quite the same though)

    The fact, that you didn't have the issue doens't mean it's easy for others.
     
    News123, Aug 20, 2010
    #10
  11. On 20-Aug-2010, at 1:17 PM, News123 wrote:

    > On 08/20/2010 02:26 AM, Steven D'Aprano wrote:
    >> On Thu, 19 Aug 2010 22:00:16 +0000, Martin Gregorie wrote:
    >>
    >>> Recursion can be quite a trick to get your mind round at first

    >>
    >> Really? Do people actually find the *concept* of recursion to be tricky?

    > Is this a sincere surprise or are you just boasting?
    >>
    >> If I remember correctly, my puzzlement about recursion lasted about 15
    >> seconds. I remember thinking "How does the function foo know that there
    >> is a function foo when foo doesn't fully exist yet?", but once I accepted
    >> the fact that it just does it all just seemed obvious. Getting recursion
    >> *right* is sometimes tricky, but the idea itself isn't.

    >
    > Well there's two things where I remember, that at least quite some
    > people in our class (at least the ones who didn't do maths or
    > programming in their spare time) had problems with.
    >
    > This were recursion and Mathematical induction. (quite the same though)
    >
    > The fact, that you didn't have the issue doens't mean it's easy for others.
    >
    >
    >
    > --
    > http://mail.python.org/mailman/listinfo/python-list


    Well I guess why you did not have a problem understanding recursion is because you took for granted that it is the way it is.
    Most people, like me, try to reason why something is the way it is ! Hence, the delay in understanding the concept fully.
     
    Navkirat Singh, Aug 20, 2010
    #11
  12. On Fri, Aug 20, 2010 at 12:47 AM, News123 <> wrote:
    > On 08/20/2010 02:26 AM, Steven D'Aprano wrote:
    >> On Thu, 19 Aug 2010 22:00:16 +0000, Martin Gregorie wrote:
    >>
    >>> Recursion can be quite a trick to get your mind round at first

    >>
    >> Really? Do people actually find the *concept* of recursion to be tricky?

    > Is this a sincere surprise or are you just boasting?


    I think his point is that the confusion is on how to do it right, not
    the concept of it.

    Geremy Condra
     
    geremy condra, Aug 20, 2010
    #12
  13. Steven D'Aprano a écrit :
    > On Thu, 19 Aug 2010 22:00:16 +0000, Martin Gregorie wrote:
    >
    >> Recursion can be quite a trick to get your mind round at first

    >
    > Really? Do people actually find the *concept* of recursion to be tricky?
    >


    I onced worked in a shop (Win32 desktop / accouting applications mainly)
    where I was the only guy that could actually understand recursion. FWIW,
    I also was the only guy around that understood "hairy" (lol) concepts
    like callback functions, FSM, polymorphism, hashtables, linked lists,
    ADTs, algorithm complexity etc...

    Needless to say, I didn't last long !-)
     
    Bruno Desthuilliers, Aug 20, 2010
    #13
  14. Salut !

    C'est cela, la solitude du programmeur génial...

    @-salutations
    --
    Michel Claveau
     
    Michel Claveau - MVP, Aug 20, 2010
    #14
  15. Michel Claveau - MVP a écrit :
    > Salut !
    >
    > C'est cela, la solitude du programmeur génial...
    >
    > @-salutations


    Moi aussi je t'aime, Michel !-)
     
    Bruno Desthuilliers, Aug 20, 2010
    #15
  16. Baba

    John Nagle Guest

    On 8/20/2010 12:47 AM, News123 wrote:
    > On 08/20/2010 02:26 AM, Steven D'Aprano wrote:
    >> On Thu, 19 Aug 2010 22:00:16 +0000, Martin Gregorie wrote:
    >>
    >>> Recursion can be quite a trick to get your mind round at first

    >>
    >> Really? Do people actually find the *concept* of recursion to be tricky?

    > Is this a sincere surprise or are you just boasting?
    >>
    >> If I remember correctly, my puzzlement about recursion lasted about 15
    >> seconds. I remember thinking "How does the function foo know that there
    >> is a function foo when foo doesn't fully exist yet?", but once I accepted
    >> the fact that it just does it all just seemed obvious. Getting recursion
    >> *right* is sometimes tricky, but the idea itself isn't.


    If you think about what the implementation has to do, it's quite
    complicated. Which objects are copied, and which are merely
    referenced? Is the recursion going to result in control being
    inside the same object instance twice? Is the recursion a closure?
    Is tail recursion possible, and does your language implement it?

    Python does not do tail recursion, so using recursion
    where iteration could do the job is generally a bad idea. Scheme, on
    the other hand, always does tail recursion where possible.

    Python does have generators, and I recently wrote a recursive
    generator for a production application. I needed to descend a
    specialized directory tree structure (the one used by the US
    Securities and Exchange Commission to store filings) and
    retrieve the last N days of filings. So I have a recursive
    generator that returns directory after directory, descending
    into the directories for years and quarters as necessary.
    The calling function stops calling the generator when it
    has found the information it needs, which happens before
    the generator runs out. That's a real-life use case
    for such a construct, and led to much shorter code than
    a non-recursive implementation.

    John Nagle
     
    John Nagle, Aug 20, 2010
    #16
  17. Baba

    Neil Cerutti Guest

    On 2010-08-20, John Nagle <> wrote:
    > Python does not do tail recursion, so using recursion where
    > iteration could do the job is generally a bad idea. Scheme, on
    > the other hand, always does tail recursion where possible.


    A tail-recursive function is usually easy to convert to a
    loop-style iteration. However, Scheme does tail-call
    optimization, I believe, which is slightly more general.

    --
    Neil Cerutti
     
    Neil Cerutti, Aug 20, 2010
    #17
  18. Baba

    John Bokma Guest

    John Nagle <> writes:

    > Python does not do tail recursion, so using recursion
    > where iteration could do the job is generally a bad idea. Scheme, on
    > the other hand, always does tail recursion where possible.


    I think you mean tail recursion optimization / elimination.
    Python does tail recursion:

    >>> def x(n):

    .... if n == 10: return
    .... print n
    .... x(n + 1)
    ....
    >>> x(1)

    1
    2
    3
    4
    5
    6
    7
    8
    9


    --
    John Bokma j3b

    Blog: http://johnbokma.com/ Facebook: http://www.facebook.com/j.j.j.bokma
    Freelance Perl & Python Development: http://castleamber.com/
     
    John Bokma, Aug 20, 2010
    #18
  19. Baba

    Baba Guest

    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
     
    Baba, Aug 21, 2010
    #19
  20. Baba

    Baba Guest

    On Aug 19, 11:00 pm, Martin Gregorie <>
    wrote:

    > By way of a hint, here are two versions of the classic example of
    > recursion: calculating factorials. Recursion can be quite a trick to get
    > your mind round at first, so compare the two and follow through their
    > operation step by step...


    Hi Martin

    Thanks for your post. This basic but fundamental computation
    (calculating factorials) 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
     
    Baba, Aug 21, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tuurbo46

    iterative structue

    Tuurbo46, Oct 5, 2005, in forum: Java
    Replies:
    0
    Views:
    620
    Tuurbo46
    Oct 5, 2005
  2. Booser
    Replies:
    1
    Views:
    1,282
    CBFalconer
    Feb 9, 2004
  3. BQ
    Replies:
    14
    Views:
    758
    Richard Bos
    Mar 25, 2005
  4. V
    Replies:
    4
    Views:
    672
    Ben Bacarisse
    May 13, 2008
  5. Ania
    Replies:
    15
    Views:
    724
Loading...

Share This Page