[FIXED] Find max element using recursion

Issue

I am new to recursion and the task is to find the POSITION of largest element in the array using recursion. This is my code:

def calc(low , high):
    print(low, high)
    if low == high:
        return low
    max_1 = calc(low , low +high//2)
    max_2 = calc(low + high//2 , high)
    if a[max_1] > a[max_2]:
        return max_1
        
a = [4,3,6,1,9]
print(calc(0 , len(a)))

What am I doing wrong? While google gives me solutions for finding the max element in array none of them have solutions for finding position of max element. Thanks in advance.

Solution

You are almost there. Two tiny mistakes are:

• Base case should be low + 1 == high
• Mid point should be (low + high) // 2

def calc(low , high):
    if low + 1 == high:
        return low 
    max_1 = calc(low , (low + high) // 2)
    max_2 = calc((low + high) // 2 , high)
    if a[max_1] > a[max_2]:
        return max_1
    else:
        return max_2
        
a = [4,3,6,1,9]

print(calc(0 , len(a)))
## 4

Your solution generates infinite recursion due to the wrong base case and the mid-point.

When low == 0 and high == 1, since low != high you trigger two calls

max_1 = calc(low , low + high // 2) 
max_2 = calc(low + high // 2 , high)

which are evaluated to

max_1 = calc(0, 0) ## This got returned to 0, because low == high
max_2 = calc(0, 1) ## Notice here again low == 0 and high == 1

The second call max_2 = calc(0, 1) triggers again another two calls one of which is again max_2 = calc(0, 1). This triggers infinite recursions that never returns back to max_2 and max_2 will never get evaluated and thus neither the lines after it (if a[max_1] > a[max_2]: ... ).

That is why you should check for base case low + 1 == high instead of low == high. Now you could test yourself and guess if the following code will generate infinite recursion or not. Will this time max_2 gets returned value assigned to it and the lines after it get evaluated?

def calc(low , high):
    if low + 1 == high: # Here is changed from your solution
        return low 
    max_1 = calc(low , low + high // 2) # Here is same to your solution
    max_2 = calc(low + high // 2 , high) # Here is same as well
    if a[max_1] > a[max_2]:
        return max_1
    else:
        return max_2

If you get the answer right, you are half way in understanding your mistake. Then you can play with different mid-point and print at each level of recursion to see how that affects results and get a full understanding.

Answered By - englealuze