431,900 Members | 1,078 Online
Need help? Post your question and get tips & solutions from a community of 431,900 IT Pros & Developers. It's quick & easy.

# Scope Problem

 P: n/a 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 Jul 18 '05 #1
5 Replies

 P: n/a 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 Jul 18 '05 #2

 P: n/a 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 Jul 18 '05 #3

 P: n/a 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 Jul 18 '05 #4

 P: n/a "Nickolay Kolev" 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 Jul 18 '05 #5

 P: n/a 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 "", line 1, in ? File "", line 6, in index File "", line 6, in index File "", line 6, in index File "", line 6, in index File "", line 6, in index File "", line 6, in index File "", line 6, in index File "", line 6, in index File "", 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 Jul 18 '05 #6

### This discussion thread is closed

Replies have been disabled for this discussion.