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

 

[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

 

[Irmen de Jong]

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/Cookbook/Python/Recipe/54159

Good luck!
--Irmen

 

[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.]

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.
.... try:
.... if seq[n] == value:
.... return n
.... else:
.... return index(seq, value, n+1)
.... except IndexError:
.... return -1
....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