Recursion and return for finding index of value

Question

So I came across an exercise problem in one of my CSE 101 slides and the problem asked to find a value in a list or a string using recursion. If the value was inside the list or the string, return the first index position that matches the value. I was able to solve it but I don't understand why it works. Here is my code:

def rindex(a, pos):
 if pos not in a:
 return None
 elif pos in a:
 if a[0] != pos:
 return rindex(a[1:], pos) + 1
 return 0

Specifically, I don't understand why

return 0

makes my function work. Why does it return the correct value rather than 0?

• S.L. Barth is on codidact.com: It's the stop condition of your recursion. You could try stepping through your code manually. And/or experiment by giving it different values and try to understand the results.
• tripleee: Imagine each if without an else has an else: pass and figure out under what conditions you end up taking this code path.

Answer 1

Every time a return is encountered in your function the result is returned and the function execution stops. This means that return 0 will never be encountered in the event of pos existing in the current a slice except when the first element of the current slice equals to pos - at that point you return 0 to indicate that the index should not be increased. If you were not to return it, rindex() would return None by default causing an error when you try to sum it with + 1 up the recursion chain.

That being said, whenever you do if pos not in a: you're iterating over the list a in search of pos so your code will be immensely inefficient (especially since you're then doing the exact same search again in the elif block whereas simple else would more than suffice). You can reformulate your code as:

def rindex(a, pos):
 if a[0] == pos: # element found, do not increase the index
 return 0
 return rindex(a[1:], pos) + 1

So you're only doing slices instead of two iterations on each recursion. The biggest issue here is that it will raise an IndexError if pos is not found as the list recursion reaches the end. You can capture that and return any sort of value if you prefer value returns over exceptions, so in your case:

def rindex(a, pos):
 if a[0] == pos: # element found, do not increase the index
 return 0
 try:
 return rindex(a[1:], pos) + 1
 except (IndexError, TypeError): # capture both to propagate
 return None

However, keep in mind that even doing list slices is not the most perfomant solution, especially when memory is concerned. Since Python passes names to references you can recurse over your whole list instead with little to no penalty and use indexes to traverse over the list recursively, i.e.:

def rindex(a, pos, loc=0):
 if a[loc] == pos:
 return loc
 return rindex(a, pos, loc+1)

And you don't even have to do a recursive try .. except choreography to capture the errors - you can do it directly in the function either preemptive (LBYL style):

def rindex(a, pos, loc=0):
 if len(a) >= loc:
 return None
 if a[loc] == pos:
 return loc
 return rindex(a, pos, loc + 1)

Or after the fact (EAFP style):

def rindex(a, pos, loc=0):
 try:
 if a[loc] == pos:
 return loc
 except IndexError:
 return None
 return rindex(a, pos, loc + 1)

These also allow you to pass an arbitrary index as well (i.e. -1) when element is not-found as the validation is separated from the actual index search so it wont affect the index sum.