Velocity Reviews > Iterative vs. Recursive coding

# Iterative vs. Recursive coding

Baba
Guest
Posts: n/a

 08-19-2010
Level: Beginner

exercise source:
http://ocw.mit.edu/courses/electrica...ents/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("atgacatgcacaagtatgca t","atgacatgcacaagtatgcatatgc")

tnx
Baba

Thomas Jollans
Guest
Posts: n/a

 08-19-2010
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("atgacatgcacaagtatgca t","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-conte...mming-Book.jpg

- Thomas

PS: If you think you're thinking, then you're really only thinking that
you're thinking. Or are you?

MRAB
Guest
Posts: n/a

 08-19-2010
Baba wrote:
> Level: Beginner
>
> exercise source:
> http://ocw.mit.edu/courses/electrica...ents/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("atgacatgcacaagtatgca t","atgacatgcacaagtatgcatatgc")
>

'countSubStringMatchRecursive' isn't recursive at all.

Martin Gregorie
Guest
Posts: n/a

 08-19-2010
On Thu, 19 Aug 2010 14:12:44 -0700, Baba wrote:

> Level: Beginner
>
> exercise source:
> http://ocw.mit.edu/courses/electrica...-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 |

Dave Angel
Guest
Posts: n/a

 08-19-2010

Baba wrote:
> Level: Beginner
>
> exercise source:
> http://ocw.mit.edu/courses/electrica...ents/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("atgacatgcacaagtatgca t","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

MRAB
Guest
Posts: n/a

 08-19-2010
Thomas Jollans wrote:
[snip]
> "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-conte...mming-Book.jpg
>

The definition for recursion looks a lot like that for infinite loop.
Perhaps because it's tail-recursive?

Steven D'Aprano
Guest
Posts: n/a

 08-20-2010
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?

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

John Nagle
Guest
Posts: n/a

 08-20-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/...on-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

Dennis Lee Bieber
Guest
Posts: n/a

 08-20-2010
On Thu, 19 Aug 2010 14:12:44 -0700 (PDT), Baba <(E-Mail Removed)>
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://www.velocityreviews.com/forums/(E-Mail Removed) HTTP://wlfraed.home.netcom.com/

News123
Guest
Posts: n/a

 08-20-2010
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.