Python Function Recursive - Give Index of first occurence of 'number' in 'list'-CodePudding

I have an exercice where I need to find the index of the first occurence of a number in list. But I also need to return None if index can't be found, meaning the number is not in list. I need to do that with a recursive function in Python.

I already created a code that does: "find the index of the first occurence of a number in list". And it works.

def index(lst, number_find):
    if lst == []:
        return None
    elif lst[0] == number_find:
        return 0
    else:
        return 1   index(lst[1:], number_find)

liste = range(51)
print(index(liste, 42))

But I can't write the code that manages the case if the number is not in list. I have done that:

def index(lst, number_find):
    if number_find not in lst: 
        return None
    elif lst == []:
        return None
    elif lst[0] == number_find:
        return 0
    else:
        return 1   index(lst[1:], number_find)

liste = range(51)
print(index(liste, 42))

But the use of "not in" is not good here for me because that seems to use some iterative code that I can't use.

CodePudding user response：

You have to protect against the case where None comes back from the recursive call, because 1 None will raise a TypeError:

def index(lst, number_find):
    if lst == []:
        return None
    elif lst[0] == number_find:
        return 0
    else:
        i = index(lst[1:], number_find)
        if i is not None:
            return 1   i
        return None  # not strictly necessary as None returned implicity

Of course, when you return from every if-block, you can omit any else. Also, None is the default return value, so you can shorten your logic

def index(lst, number_find):
    if lst:
        if lst[0] == number_find:
            return 0
        if (i := index(lst[1:], number_find)) is not None:
            return 1   i

Btw, since slicing is O(N) here, all these approaches are quadratic. So here is a solution that has linear complexity:

def index(lst, number_find):
    def rec(it, i=0):
        if (n := next(it, None)) is not None:
            return i if n == number_find else rec(it, i 1)
    return rec(iter(lst))

CodePudding user response：

The accepted answer by user2390182 explains in detail how to handle the possible None value returned by the recursive call.

A different approach is to write the function in a tail-recursive way:

def index(lst, number_find, acc=0):
  if lst == []:
    return None
  elif lst[0] == number_find:
    return acc
  else:
    return index(lst[1:], number_find, acc 1)

Note that python doesn't perform tail-rec optimization; but this approach still avoids the 1 None issue.