Recursion and return for finding index of value

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?

if

else

else: pass

1 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.

return

return 0

pos

a

pos

0

rindex()

None

+ 1

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:

if pos not in a:

a

pos

elif

else

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:

IndexError

pos

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):

try .. except

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.

-1

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.