2

I wrote a little bit code try to search a word in a list. It's not the final version and basically it can't do anything yet. However, I don't understand what was wrong with the code:

def findword (word, t):
    t.sort()
    midword = t[len(t)/2]
    midindex = len(t)/2
    if word > midword:
        del t[:midindex]
        findword (word, t)
    elif word < midword:
        del t[midindex+1:]
        findword (word, t)
    elif word == midword:
        return t
    else:
        return None

mydic=['apple','banana','peach','pear','melon','lemon','grape','berry']
mydic1 = findword('apple', mydic)

I got a RuntimeError: maximum recursion depth exceeded in cmp error when tried to search apple and when I search the other words in the list, it returns empty list.

Please help me figure out what was wrong. Thanks!

Improve this question
5
  • You need more debugging print/logging statements, which would make it fairly obvious what's going wrong. Commented Jun 20, 2014 at 18:19
  • 1
    Also, instead of modifying the list you're searching through, only modify the current index and the upper and lower bounds where to search. Google 'binary search' if stuck. Commented Jun 20, 2014 at 18:22
  • OP: slightly off-topic, but if you're not in Python2 you've got a scary line in there that should use __floordiv__ instead of __truediv__!! Commented Jun 20, 2014 at 19:02
  • @Noelkd I think he's using the layman definition of "dictionary" in his variable. It's a list of words :) Commented Jun 20, 2014 at 19:04
  • ..that will teach me for being a smart arse thanks @AdamSmith Commented Jun 21, 2014 at 7:35

4 Answers 4

Reset to default
3

Take a look at this code segment:

    elif word < midword:
        del t[midindex+1:]
        findword (word, t)

In your code, you will come to a point that the list is reduced to just two elements, that is:

t == ['apple', 'banana']

In which case, take a look at the following interactive session:

In [15]: t = ['apple', 'banana']

In [16]: midindex = len(t)/2

In [17]: midindex
Out[17]: 1

In [18]: t[midindex+1:]
Out[18]: []

In [19]: del t[midindex+1:]

In [20]: t
Out[20]: ['apple', 'banana']

Notice that in line 19, you deleted nothing, t remains the same, then you called findword with the same list and run into infinite recursion until you run out of stack space. You should redesign your code to overcome this problem.

Another problem I see is you simply called findword recursively, but did not make use of the return value. Instead of:

    elif word < midword:
        del t[midindex+1:]
        findword (word, t)

you should do:

    elif word < midword:
        del t[midindex+1:]
        return findword (word, t)

Additional Suggestions

  • Do not put the t.sort() inside the findword function. Sorting could be expensive, so you should only do it once, outside of findword.
  • As others pointed out, it is a bad practice to modify the list, instead redesign your code not to do that
  • If this is not a homework or exercise, I suggest to use a set if you want fast look-up
  • Python has a library module called bisect which will do binary search.
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks Hai! Your answer is exactly what I'm looking for. Now I understand why it keeps calling itself and causes overflow.
2

Implementation of Binary Search

First of all, recursion is yucky. Avoid that if you can -- it can cause these kinds of MaxRecursion errors in very huge search spaces when you're unlucky.

Let's switch this to iterative, and see what we can do:

def binary_search(lst, word):
    new_lst = sorted(lst) # so we only do this once
    return _binary_search(new_lst, word, start=0, end=len(new_lst))

def _binary_search(lst, word, start, end):
    while end - start > 0: # technically this is just while end-start but...
        pivot = (start + end) // 2 # floordiv!
        pivot_element = lst[pivot]
        if word > pivot_element:
            start = pivot + 1
        elif word < pivot_element:
            end = pivot
        else: # word == pivot_element
            return word
    else: return None

>>> my_list = ['apple', 'banana', 'peach', 'pear', 'melon', 'lemon', 'grape', 'berry']
>>> print(binary_search(my_list, "strawberry"))
None
>>> print(binary_search(my_list, "pear"))
"pear"
Improve this answer

2 Comments

Great idea of adding first and last as function argument. It doesn't modify the list and still narrower the search space within each recursion. Thanks!
@homerMeng thanks. I don't think I'd ever actually built a binary search engine before, so it was nice to flex my algorithmic muscle
1

If you are just trying to search for a word in a list, you can do this--

mydic=['apple','banana','peach','pear','melon','lemon','grape','berry']

inputword = 'apple'
if inputword in mydic:
    print('yes it is in the list')
else:
    print('no it is not')
Improve this answer

1 Comment

OP is trying to implement a recursive binary search. I'm sure they know how to test for membership :)
0

You cant change your dictonary in run time as you are doing. And in your code you do not have return in you recursion calls.

def findword (word, t):
   for i in t:
      if i == word:
         return i

Or if you still prefer use binary search:

def findword (word, t):
    t.sort()
    return findword_aux(word, t, 0, len(t)-1)

def findword_aux(word, array, first, last):
    midindex = (first + last) / 2 
    midword = array[midindex]
    if last - first == 1:
        return None
    if word == midword:
        return  midword
    elif word > midword:
        return findword_aux (word, array, midindex+1, last)
    elif word < midword:
        return findword_aux (word, array, first, midindex-1)

def run_tests():
    test1()
    test2()

def test1():
    mydic=['apple','banana','peach','pear','melon','lemon','grape','berry'] 
    result = findword('apple', mydic)
    if result == 'apple':
        print 'test1 pass'
    else:
        print 'test1 error'

def test2():
    mydic=['apple','banana','peach','pear','melon','lemon','grape','berry'] 
    result = findword('pinapple', mydic)
    if result == None:
        print 'test2 pass'
    else:
        print 'test2 error'
Improve this answer

2 Comments

findword_aux will return None if one of your search spaces is exactly one, but that element is exactly the target.
Adam was right. I'm testing your code and see what should be the fix. Thanks anyway!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.