For an assignment, I have to find the maximum element's index recursively. How can I do that?
I've tried the following function, but I keep getting wrong results:
def maxElement(A):
if len(A)==1:
return A[0]
else:
max=maxElement(A[1:])
if A[0]>max:
return A[0]
else:
return max
A=[9, 16, 100, 36, 4, 25, 1, 81, 49, 9, 64]
print(maxElement(A))
I should get 2, since it's the third element, but I keep getting 100.
the simple way is with max and index as @Harwee show, but you can also do both with this recursive function
def find_max_pos(lista,pos=0,pos_item=None) -> "(index,item)":
if not lista:
return pos_item
else:
item = lista[0]
resto = lista[1:]
if pos_item is None:
return find_max_pos(resto,pos+1,(pos,item))
prev = pos_item[1]
if prev >= item:
return find_max_pos(resto,pos+1,pos_item)
else:
return find_max_pos(resto,pos+1, (pos,item) )
with this you keep track of your current position with the pos argument and the max item and its position with the pos_item, the base case is the empty list in with case you return what you have and in each iteration you reduce the list, you can modify this so you don't keep copying the list over an over with additional arguments max_pos like this
def find_max_pos_v2(lista,pos=0,pos_item=None,max_pos=None) -> "(index,item)":
if max_pos is None:
max_pos = len(lista)
if pos >= max_pos:
return pos_item
item = lista[pos]
if pos_item is None:
return find_max_pos_v2(lista,pos+1,(pos,item),max_pos)
prev = pos_item[1]
if prev >= item:
return find_max_pos_v2(lista,pos+1,pos_item,max_pos)
else:
return find_max_pos_v2(lista,pos+1,(pos,item),max_pos )
if you only want the position or the max element modify the use of pos_item accordingly.
Notice that I make all additional arguments default to some convenient value and handle then accordingly.
example
>>> A=[9, 16, 100, 36, 4, 25, 1, 81, 49, 9, 64]
>>> find_max_pos(A)
(2, 100)
>>> find_max_pos_v2(A)
(2, 100)
>>>
You just need to keep track of the max element its index and the current index as you go, returning the index of the max element:
def max_ind(l, i, mx, mx_i):
if not l:
return mx_i
if l[0] > mx:
mx = l[0]
mx_i = i
i += 1
return max_ind(l[1:], i, mx, mx_i)
l = [9, 16, 100, 36, 4, 25, 1, 81, 49, 9, 64]
print(max_ind(l, 0, l[0], 0))
2
If you want the element and the index:
def max_ind(l, i, mx, mx_i):
if not l:
return mx_i, mx
if l[0] > mx:
mx = l[0]
mx_i = i
i += 1
return max_ind(l[1:], i, mx, mx_i)
l = [9, 16, 100, 36, 4, 25, 1, 81, 49, 9, 64]
print(max_ind(l, 0, l[0], 0))
(2, 100)
You can also do it without slicing:
def max_ind(l, mx, i, mx_i):
if not l.__length_hint__():
return mx_i
e = next(l)
if e > mx:
mx = e
mx_i = i
i += 1
return max_ind(l, mx, i, mx_i)
l = [9, 16, 100, 36, 4, 25, 1, 81, 49, 9, 64]
print(max_ind(iter(l), l[0], 0, 0))
I don't know what you meant something similar to this this will do the job
A=[9, 16, 100, 36, 4, 25, 1, 81, 49, 9, 64]
x = max(A)
print A.index(x)
