Scope Problem

[Nickolay Kolev]

Hi all,

I have set to implementing a few basic algorithms in Python serving a
twofold purpose: learning the algorithms and learning Python a little
better.

I have however encountered a strange (for me anyway) scoping problem.

Here is my implementation of linear search as a method in a class, hence
all the self's (self.sequence is the sorted sequence we are searching in
and value is, well, the value we are searching for):

def linearSearch(self, value, index = None):

if not index:
index = 0

try:

if self.sequence[index] == value:

return index

else:

self.linearSearch(value, index + 1)

except IndexError:

return -1
My problem is that this method always returns None regardless of whether
the value was found or not. If I put print statements in there, all the
values and indices are printed correctly though. Actually I have another
parameter to this method called debug, if this is set, the single
comparison steps are printed to STDOUT (omitted above to avoid clutter).

What am I doing wrong?

Many thanks in advance,
Nicky

[Irmen de Jong]

Nickolay Kolev wrote:

I have however encountered a strange (for me anyway) scoping problem.
This has nothing to do with scoping.
Here is my implementation of linear search as a method in a class, hence
all the self's (self.sequence is the sorted sequence we are searching in
and value is, well, the value we are searching for):

def linearSearch(self, value, index = None):

if not index:
index = 0
try:
if self.sequence[index] == value:
return index
else:
self.linearSearch(value, index + 1) In this line, you don't return a value from the recursive call.
Change it to:
return self.linearSearch(value, index + 1)
except IndexError:
return -1

The algorithm should now work, although it is very inefficient.
Now, you're learning Python, so it's probably good to point
out that a containment test is usually done like so:

if value in sequence: ...

If you want to have the index:

idx = sequence.index(value)

And for quick (much quicker than linear) search in a sorted sequence,
have a look at the bisect module etc:
http://aspn.activestate.com/ASPN/Coo...n/Recipe/54159

Good luck!
--Irmen

[Daniel Dittmar]

You are not returning the value of the recursive call
self.linearSearch(value, index + 1).

Hmm, implementing a linear search through recursion. Is your first language
LISP?

Daniel

Nickolay Kolev wrote:

Hi all,

I have set to implementing a few basic algorithms in Python serving a
twofold purpose: learning the algorithms and learning Python a little
better.

I have however encountered a strange (for me anyway) scoping problem.

Here is my implementation of linear search as a method in a class,
hence all the self's (self.sequence is the sorted sequence we are
searching in and value is, well, the value we are searching for):

def linearSearch(self, value, index = None):

if not index:
index = 0

try:

if self.sequence[index] == value:

return index

else:

self.linearSearch(value, index + 1)

except IndexError:

return -1
My problem is that this method always returns None regardless of
whether the value was found or not. If I put print statements in
there, all the values and indices are printed correctly though.
Actually I have another parameter to this method called debug, if
this is set, the single comparison steps are printed to STDOUT
(omitted above to avoid clutter).

What am I doing wrong?

Many thanks in advance,
Nicky

[Nickolay Kolev]

Thanks guys,

I should have seen it myself, it´s stupid enough.

@Irmen: I am implementing the algorithms not for the purpose of using
them, but for the purpose of learning them. I thinks it is a bit early
for trying to outsmart the python dev-people. :-)

@Daniel: It should be pretty obvious form my mistake that it is not. A
real Lisper would never do such a thing. :-)

Thanks again,
Nicky

[Tom B.]

"Nickolay Kolev" <nm*****@uni-bonn.de> wrote in message
news:ce**********@f1node01.rhrz.uni-bonn.de...

Hi all,

I have set to implementing a few basic algorithms in Python serving a
twofold purpose: learning the algorithms and learning Python a little
better.

I have however encountered a strange (for me anyway) scoping problem.

Here is my implementation of linear search as a method in a class, hence
all the self's (self.sequence is the sorted sequence we are searching in
and value is, well, the value we are searching for):

def linearSearch(self, value, index = None):

if not index:
index = 0

try:

if self.sequence[index] == value:

return index

else:

self.linearSearch(value, index + 1)

except IndexError:

return -1
My problem is that this method always returns None regardless of whether
the value was found or not. If I put print statements in there, all the
values and indices are printed correctly though. Actually I have another
parameter to this method called debug, if this is set, the single
comparison steps are printed to STDOUT (omitted above to avoid clutter).

What am I doing wrong?

Many thanks in advance,
Nicky

Try useing the self keyword,

def linearSearch(self, value, index = None): self.index = index

if not self.index :
self.index = 0

try:

if self.sequence[self.index ] == value:

return self.index

else:

self.linearSearch(value, self.index + 1)

except IndexError:

return -1

Tom

[Peter Otten]

Nickolay Kolev wrote:

Python doesn't support tail recursion; your algorithm is not only
inefficient but incorrect. The number of allowed recursion levels is
significantly below the maximum number of list entries.

import sys
sys.setrecursionlimit(10) # reduced for demonstration purposes
def index(seq, value, n=0): .... try:
.... if seq[n] == value:
.... return n
.... else:
.... return index(seq, value, n+1)
.... except IndexError:
.... return -1
.... index(range(5), "a") -1 index(range(10), "a")

Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 6, in index
File "<stdin>", line 6, in index
File "<stdin>", line 6, in index
File "<stdin>", line 6, in index
File "<stdin>", line 6, in index
File "<stdin>", line 6, in index
File "<stdin>", line 6, in index
File "<stdin>", line 6, in index
File "<stdin>", line 6, in index
RuntimeError: maximum recursion depth exceeded

The

def f(value=None):
if value is None:
# set real default

idiom is only needed for mutable default values.
@Irmen
@Daniel

I see finally someone is embracing the decorator style slated for 2.4 :-)

Peter