How does the return work inside a recursive function in Python?

Question

I am having issues when returning the values from a recursive function. For example, in a very simple function called 'RBinSearch', I am trying to find the index of the key in an array. Unfortunately, I just cannot able to return the value (answer should be 4) based on my understanding.

For comparison, I have used a normal function with a loop to test the return (in a function called 'BinarySearch' here), which is working as expected. Can anyone please explain how the return behave inside a recursive function and where my understanding is incorrect? Thanks!

import math
import sys

def BinarySearch(array, key):
    low=0
    high=len(array)-1
    while(low<=high):
        mid=math.floor((low+high)/2)
        if(key==array[mid]):
            return mid
        elif(key<array[mid]):
            high=mid-1
        elif(key>array[mid]):
            low=mid+1
            
    return -1

def RBinSearch(array,low,high,key):
    if(low<=high):
        mid=math.floor((low+high)/2)
        print("Value of mid: ",mid)
        if(key==array[mid]):
            print("Found the value: ",mid)
            return mid
            sys.exit()
                                   
        elif(key<array[mid]):
            RBinSearch(array, low, mid-1, key)
        else:
            RBinSearch(array, mid+1, high, key)
    return -1
arr=[4,8,10,15,18,21,24,27,29,33,34,37,39,41,43]
print("Index from while Bin search: ",BinarySearch(arr, 18))
print("The index found using the Binary search is: ",RBinSearch(arr, 0,len(arr)-1,18))

Output

You use recursion to find the correct spot - and then ignore the result, and return -1. You want return RBinSearch(...) instead. Also, stylewise, in Python you should use snake_case for functions (and variables); TitleCase is conventionally used for class names. — Amadan
– Amadan, Commented Dec 10, 2021 at 11:19
@Amadan Sure, but how to return the result after getting the value in a recursive function? In this example, I would like to return the value of variable 'mid' in RBinSearch but the function keeps returning -1. Why does this happen? — aspiringroboticist
– aspiringroboticist, Commented Dec 10, 2021 at 11:26
As I described, and as Ratery answered, but using return to pass the subordinate result back. Your terminal invocation returns mid, but it returns it only one level up; the intermediate levels were not propagating that value further up. They were returning -1 instead. tl;dr: The function kept returning -1 because you told it to. :) — Amadan
– Amadan, Commented Dec 10, 2021 at 13:06
Imagine an analogy, a fire bucket chain. You tell the people "If you're next to the river, fill up the bucket and give it to the next guy. If not, carefully grip the bucket given to you, and yell that you received it." How far do you see water going? Just up to the second guy, because you didn't tell the people away from the river to pass the bucket along. — Amadan
– Amadan, Commented Dec 10, 2021 at 13:09

Ratery · Accepted Answer · 2021-12-10 11:23:09Z

2

You need to return RBinSearch result in your RBinSearch function:

def RBinSearch(array, low, high, key):
    if low <= high:
        mid = math.floor((low + high) / 2)
        print("Value of mid: ", mid)
        if key == array[mid]:
            print("Found the value: ", mid)
            return mid

        elif key < array[mid]:
            return RBinSearch(array, low, mid - 1, key)
        else:
            return RBinSearch(array, mid + 1, high, key)
    return -1

Also you shouldn't use sys.exit().

answered Dec 10, 2021 at 11:23

Ratery

2,9521 gold badge7 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How does the return work inside a recursive function in Python?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related