Find max element using recursion

Question

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.

You are doing binary search in an unsorted array and you compute the middle point wrong. You need to use a linear search. — fafl
– fafl, Commented May 12, 2022 at 10:52
@fafl i am tryna use divide and conquer to solve this problem. So I dont think it matters if the array is sorted or not. — eyah
– eyah, Commented May 12, 2022 at 11:07
low + high//2 is not the middle element, you're missing parentheses. — interjay
– interjay, Commented May 12, 2022 at 11:09

englealuze · Accepted Answer · 2022-05-12 13:52:30Z

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.

Stuart · Accepted Answer · 2022-05-12 13:04:24Z

1

I think this is what you are trying to do. You should pass list slices to the function - this makes it much simpler than trying to pass low and high indices, and avoids accessing the list as a global variable - and add the midpoint to the resulting index that comes from the right hand side of the list.

def idxmax(l):
    if len(l) == 1:
        return 0
    midpoint = len(l) // 2
    a = idxmax(l[:midpoint])
    b = idxmax(l[midpoint:]) + midpoint
    if l[a] >= l[b]:
        return a
    else:
        return b

print(idxmax([4,3,6,1,9]))

This returns the index of the first occurrence of the maximum, e.g. idxmax([4,9,3,6,1,9]) == 1

If you want to implement it by passing indices instead of slices (possibly more efficient by not making multiple copies of the list), you could do it like this:

def idxmax(l, start=0, end=None):
    if end is None:
        end = len(l) - 1
    if end == start:
        return start
    midpoint = (start + end) // 2
    a = idxmax(l, start, midpoint)
    b = idxmax(l, midpoint + 1, end)
    if l[a] >= l[b]:
        return a
    else:
        return b

print(idxmax([4,3,6,1,9]))

edited May 12, 2022 at 13:04

answered May 12, 2022 at 11:38

Stuart

9,8771 gold badge24 silver badges34 bronze badges

1 Comment

eyah Over a year ago

Thank you very much. Any idea why my solution is wrong?

Ze'ev Ben-Tsvi · Accepted Answer · 2022-05-12 11:52:40Z

0

I believe the task was to find the POSITION of the max number only (and not the value itself).

So, the function starts by comparing the last value with the max value of the list and returns the length of the list (minus one) as position if True. then it is recursively called to a shorter list and compared again until it left with only one value in the list

def calc(lst):
    if lst[len(lst) - 1] == max(lst):
        return len(lst) - 1
    if len(lst) > 1:
        return calc(lst[:-1])


print(calc([0, 1, 2, 3, 4, 5, 6]))  # 6
print(calc([7, 1, 2, 3, 4, 5, 6]))  # 0
print(calc([0, 1, 8, 3, 4, 5, 6]))  # 2

edited May 12, 2022 at 11:52

answered May 12, 2022 at 11:37

Ze'ev Ben-Tsvi

1,4321 gold badge5 silver badges8 bronze badges

2 Comments

fafl Over a year ago

Using the max function is a bit like cheating here, you could just write return max(range(len(lst)), key=lambda x: lst[x])

Ze'ev Ben-Tsvi Over a year ago

@fafl I was following the task as described, to find the position of the max value (not the value) using a recursive function

Collectives™ on Stack Overflow

Find max element using recursion

3 Answers 3

Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related