python recursive function loops infinitely

Question

While trying to understand how recursion works in Python, I wrote the below function which searches a list for a given value. The idea is to sort the list then find the middle index within the ith and jth elements and comparing with the search value. The problem is that it goes into an infinite loop. I have run the statements step by step and the required result obtains. Can someone point out where I got it wrong?

def search(lst, v):
    if not('i' in locals()) and not('j' in locals()):
        i = 0
        j = len(lst)
        
        # sort 
        lst.sort()
        
    midindex = i + int((j - i)/2)
    
    if lst[midindex] > v:
        j = midindex-1       
        return search(lst, v)
    elif lst[midindex] < v:
        i = midindex+1
        return search(lst, v)
    else:
        return midindex

are `search` and `bsearch` supposed to be the same function? — Phydeaux, Oct 19 '21 at 12:33
you're updating `i` and `j` but they are not being passed into function call? — kinshukdua, Oct 19 '21 at 12:36
What is `if not('i' in locals()) and not('j' in locals())` supposed to be doing? Those local variables are never going to exist at that point in the function. — khelwood, Oct 19 '21 at 12:36
`if` will always be True because each function call has its own name scope. You have to pass the values to actually check them — h4z3, Oct 19 '21 at 12:36
It would be so easy to just step through the code with a debugger and see what happens. You would not have needed to ask this question if you had done that. Linked reference to a working solution with recursion; passing the range indices as arguments. — trincot, Oct 19 '21 at 12:39

score 1 · Answer 1 · answered Oct 19 '21 at 12:43

Your problem here is that locals is, well, local to the function you're using it in. Each time you call the function (recursively or otherwise) a new variable namespace is created, so locals will always be empty. See for example:

def foo():
    x = 1
    print("foo locals:", locals())
    bar()

def bar():
    y = 2
    print("bar locals:", locals())

foo()

The output of which will be:

foo locals: {'x': 1}
bar locals: {'y': 2}

You need to pass any variables you want to use across function calls, like i and j as arguments:

def bsearch(search_list, value, i, j):
    ...

I was trying to make it a simpler form with only two arguments. — Reef, Oct 19 '21 at 12:46

python recursive function loops infinitely

1 Answers1