Find index of element in a list using recursion

Question

def index(L,v)
 ''' Return index of value v in L '''
 pass

I need help with implementing this function using recursion. Really new to recursion stuff so any advice would help!

Note that L is a list. v is a value.

Answer 1

That works

def recursive_index(L, v):
 return 0 if L[0] == v else 1 + recursive_index(L[1:], v)

but is pretty stupid (and will only work if the value exists)

You can add if v not in L: return -1 to make it work for any case, but that is even worst.

Do it really has to be recursive?

• s4kur402: what if there are more occurences of value v in the lst?
• JBernardo: @michelle it'll find the first one, as expected

Answer 2

I assume this is homework.

So you need to understand recursion. Here's an example:

def countdown(n):
 if n == 0:
 print "Hello World!"
 else:
 print n
 countdown(n-1)

You need to start with a starting point, in your case it would probably be the 0th element.

You need an end point, which should be the length - 1 or when you find the element.

Simple if else should do here, with a modified version of countdown as above.

• s4kur402: I'm new with recursion, really having trouble mainly on what is happening in the stack data. It seems like magic to me. Would you be able to recommend any website that teaches you recursion or help you learn it better?
• Pwnna: Yeah, openbookproject.net/thinkcs/python/english2e/ch11.html and greenteapress.com/thinkpython/html/book006.html

Answer 3

Yet another way:

def rec(l,v, index=0):
 try:
 if l[index] == v:
 return index
 except IndexError:
 return -1 
 return rec(l,v,index+1)

• jena: I hope this is not due to didactical purposes, but why do you subsequently pop the first element off of the list? Since you pass the current index to the function anyway, you can just check the value at the given index. :)

Answer 4

Why would someone write recursive code for that??

>>> [1,2,4,8].index(4)
2

Answer 5

L = [1, 2, 3, 4, 5, 6, 7, 11, 13]
def index(L, v):
 if len(L) == 0:
 return -1000000
 elif L[0] == v:
 return 0
 else:
 return 1 + index(L[1:], v)
print index(L, 7)
print index(L, 13)
print index(L, 100)

* Remote Interpreter Reinitialized *

6

8

-999991

Answer 6

Assuming 0 indexing, the following code will return the index of the element if it exists, or -1 if it is not contained in the list:

def index(L, v):
 if L == []:
 return -1
 elif L[0] == v:
 return 0
 rv = index(L[1:], v)
 if rv < 0:
 return rv
 return rv + 1

Answer 7

Here a tail recursive version of it:

def indexof(elem, list_):
 return indexof_tailrec(elem, list_, 0)
def indexof_tailrec(elem, list_, index):
 if index >= len(list_):
 return None
 if list_[index] == elem:
 return index
 return indexof_tailrec(elem, list_, index + 1)

Note, however, that Python does not have tail call optimization (at least not as far as I know).

Answer 8

A recursive solution to find the first occurence of an element using Binary Search is this -

def Binary_Search(l, val, low, high):
 if low > high:
 return -1
 mid = (low+high)//2
 if len(l) == 1:
 if l[0] == val:
 return 0
 return -1
 if l[mid] == val:
 if mid == 0 or l[mid-1] != l[mid]:
 return mid
 else:
 return Binary_Search(l, val, low, mid-1)
 elif l[mid] < val:
 return Binary_Search(l, val, mid+1, high)
 else:
 return Binary_Search(l, val, low, mid-1)

Answer 9

def fi(arr,x):
 if len(arr)==0:
 return -1
 elif arr[0]==x:
 return 0
 k= fi(arr[1:],x)
 if k== -1:
 return -1
 else:
 return k+1

• Jeremy Caney: Remember that Stack Overflow isn't just intended to solve the immediate problem, but also to help future readers find solutions to similar problems, which requires understanding the underlying code. This is especially important for members of our community who are beginners, and not familiar with the syntax. Given that, can you edit your answer to include an explanation of what you're doing and why you believe it is the best approach?
• Chris: Thank you for editing your answer, but you didn't really improve it. Please re-read Jeremy Caney's comment, especially the bold part.