Iterative vs. Recursive coding

[Baba]

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

 

[Thomas Jollans]

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?

 

[MRAB]

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.

 

[Martin Gregorie]

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

 

[Dave Angel]

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

 

[MRAB]

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-content/uploads/2010/05/From-a-Programming-Book.jpg

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

 

[Steven D'Aprano]

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.

 

[John Nagle]

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))
ca is 4 times in the target string

Enjoy.

John Nagle

 

[Dennis Lee Bieber]

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:])

 

[News123]

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.

 

[Navkirat Singh]

Is this a sincere surprise or are you just boasting?

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.

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.

 

[geremy condra]

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

 

[Bruno Desthuilliers]

Steven D'Aprano a écrit :

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 !-)

 

[Michel Claveau - MVP]

Salut !

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

@-salutations

 

[Bruno Desthuilliers]

Michel Claveau - MVP a écrit :

Salut !

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

@-salutations

Moi aussi je t'aime, Michel !-)

 

[John Nagle]

Is this a sincere surprise or are you just boasting?

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

 

[Neil Cerutti]

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.

 

[John Bokma]

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:
.... if n == 10: return
.... print n
.... x(n + 1)
.... 1
2
3
4
5
6
7
8
9

 

[Baba]

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]

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