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.
CodePudding user response:
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.
CodePudding user response:
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]))
CodePudding user response:
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