What actually returns recursive function?

user_13618198 0
Viewed 44

I am trying to find second biggest number in a list of numbers. In cases when there a duplicates, the second biggest number will be the second biggest number by value. For example, in a list [3, 2, 7, 7, 5] the second biggest number should be 5.

So here is what I am doing in order to solve it.

def find_second_number(nums):
    m1 = sorted(nums)[-1]
    m2 = sorted(nums)[-2]
    if m1 == m2:
        find_second_number(sorted(nums)[:-1])
    else:
        return m2
    return m2

arr = [x for x in (input().split())] 
    
print(find_second_number(arr))

What I don't understand is, which m2 is being returned. I guess in the case when arr = [3, 2, 7, 7, 5], there will be two recursive calls of find_second_number() however, I am confused which instance of the function should return the m2.

python-3.x search algorithm
1 Answers

What I don't understand is, which m2 is being returned.

It is always the m2 of the execution context of the very first call of find_second_number. Whatever the recursive call of find_second_number returns, ... your code ignores it.

So to fix it, do:

if m1 == m2:
    return find_second_number(sorted(nums)[:-1])
else:
    return m2

However, your code is calling sorted a lot of times. This makes it quite inefficient. Even calling it once will give your algorithm a time complexity of O(log), while it can be done with linear time complexity.

For instance, this would do it:

def find_second_number(nums):
    greatest = max(nums)
    return max(m for m in nums if m < greatest)
user_54598390
Related