CODEWITHSUNDEEP
pythonrecursion
homerMeng
homerMeng

Reputation: 71

Recursion error Python

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!

Upvotes: 2

Views: 532

Answers (4)

Adam Smith
Adam Smith

Reputation: 54273

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"

Upvotes: 2

Deni Z.
Deni Z.

Reputation: 11

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')

Upvotes: 1

JonatasTeixeira
JonatasTeixeira

Reputation: 1492

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'

Upvotes: 0

Hai Vu
Hai Vu

Reputation: 40803

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.

Upvotes: 3

Related Questions