recursion with a list in python

Question

I just started learning python and there are some recursion questions that I can't seem to figure out. The most annoying one is this: I need to build a function ind(e,L) where e is an int and L is a list.

By entering e if it is in the list the output needs to be its index For example:

ind(42,[0,14,52,42,15]) -> 3

This is the code I wrote this far but the index I get is always 0. Can someone please explain to me what I am doing wrong?

def location(e,L):
 if L == []:
 return False
 elif e == L[0]:
 A = L[:-1].index(e)
 return A
 else:
 return location(e,L[1:])
print(location(14,[1,2,14,1]))

thanks :)

• Joanna: First of all, if the goal of excercise is to learn recursion and implement location function on your own, why do you use . index (that is doing exactly what you want location to do) inside? And if the goal wasn't to implement it on your own, why don't you just use index?
• Joanna: And the only case when you finish recursion if the element is present, is when e == L[0]. So how can you expect something else than 0 being returned?
• Georgy: Possible duplicate of find index of element in a list using recursion

Answer 1

You only return if e is at index 0 (you can skip the L[:-1]... term, it is always 0) and propagate that unchanged. Instead of returning the meaningless index, return the number of recursions. The simplest way is to add 1 whenever the function recurses.

def location(element, sequence):
 if not sequence:
 # e is not in the list at all
 # it is not meaningful to return an index
 raise IndexError
 elif element == sequence[0]:
 # we already know where e is
 # since we checked it explicitly
 return 0
 else:
 # keep searching in the remainder,
 # but increment recursion level by 1
 return 1 + location(element, sequence[1:])

Answer 2

I'm pretty new as well, but I think this should do the trick...

def function(e,L):
 try:
 x = 0
 for val in L:
 if e == val:
 return(x)
 else: x = x+1
 except:
 print('List provided does not contain any values')

x will count through the values and return when the index equals a value in the list. It will also return multiple matches, which might be helpful.

Answer 3

One thing to notice is that the time complexity and the space complexity of your code is O(n^2). Because L[1:] creates a new list every time! It is O(n) operation in terms of time and space.

---

One proper Pythonic way of doing it is:

def location(e, L):
 n = len(L)
 def _location(start):
 if start == n:
 raise IndexError
 if L[start] == e:
 return start
 return _location(start + 1)
 return _location(0)
print(location(14, [1, 2, 14, 1]))

Output:

2

---

Time Complexity: O(n)

Space Complexity: O(n) (Due to recursion.)

Answer 4

My solution is a bit different. I start looking for e from the right end of L. If found, then the index is simply the length of L minus 1 (since Python indexes start with 0).

This implementation does not require you to make any variable to store the index, which I think is neat.

def location(e, L):
 if L:
 if L[-1] == e:
 return len(L)-1
 else:
 return location(e, L[:-1])
 return False

Test:

>>> L = [0,14,52,42,15]
>>> location(42, L)
3

Answer 5

Shorter recursive solution:

def ind(a, b):
 def _ind(a, b):
 return False if not b else (b[0] == a or 1+_ind(a, b[1:]))
 return _ind(a, b) - 1
print(ind(42,[0,14,52,42,15]))

Output:

3

If you do not mind offsetting by one:

def ind(a, b):
 return False if not b else (b[0] == a or 1+ind(a, b[1:]))
>>>ind(42,[0,14,52,42,15]) - 1

Or, using a default parameter:

def ind(a, b, c = 0):
 return False if not b else (c if b[0] == a else ind(a, b[1:], c+1))
>>>ind(42,[0,14,52,42,15])