# Iterative vs. Recursive coding

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

1. ### BabaGuest

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

2. ### Thomas JollansGuest

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:

- 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

3. ### MRABGuest

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
4. ### Martin GregorieGuest

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
5. ### Dave AngelGuest

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
6. ### MRABGuest

MRAB, Aug 20, 2010
7. ### Steven D'ApranoGuest

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

Steven D'Aprano, Aug 20, 2010
8. ### John NagleGuest

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
9. ### Dennis Lee BieberGuest

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
10. ### News123Guest

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
11. ### Navkirat SinghGuest

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
12. ### geremy condraGuest

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
13. ### Bruno DesthuilliersGuest

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

Needless to say, I didn't last long !-)

Bruno Desthuilliers, Aug 20, 2010
14. ### Michel Claveau - MVPGuest

Salut !

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

@-salutations
--
Michel Claveau

Michel Claveau - MVP, Aug 20, 2010
15. ### Bruno DesthuilliersGuest

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
16. ### John NagleGuest

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
17. ### Neil CeruttiGuest

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
18. ### John BokmaGuest

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

Freelance Perl & Python Development: http://castleamber.com/

John Bokma, Aug 20, 2010
19. ### BabaGuest

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
20. ### BabaGuest

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