Writing a function that returns the subscript of the first occurrence of value in data or None USING-CodePudding

I have been asked to:

Write a function find(data, value) that returns the subscript of the first occurrence of value in data, or None if the value is not found. Your function cannot use loops or list comprehensions and also cannot use the index method of a list. You must use recursion only!

This is my current code:

def find(data, value):
    """Returns the subscript of the first occurrence of value in data or None"""
    if not data:
        return None
    if data[0] == value:
        return data[value]
    return find(data[1:], value)

Test code:

print(find([10, 20, 30], 0))
---> None
print(find(["hi", "there", "you"], "there"))
---> 1

I am having trouble figuring out how to return the index of the first occurrence of the value in data when found!

CodePudding user response：

Start with the two base cases: where you have an empty list and where you match the first element.

With the empty list you have it: just return None

With a match on the first item, you should return 0.

Now the recursion will just be 1 recursive_function. The wrinkle is that you need to watch out for the case where the recursive function returns None. That might look something like:

def find(data, value):
    """Returns the subscript of the first occurrence of value in data or None"""
    if not data:
        return None
    if data[0] == value:
        return 0

    n = find(data[1:], value)

    if n is not None:
        return 1   n 

    return None

print(find([10, 20, 30], 0))
#---> None
print(find(["hi", "there", "you", "there"], 'there'))
#---> 1

If you can play with the function signature, you can simplify this by keeping track of the current index in an argument starting with a default value of zero:

def find(data, value, i=0):
    """Returns the subscript of the first occurrence of value in data or None"""
    if not data:
        return None
    if data[0] == value:
        return i
    
    return find(data[1:], value, i 1)

print(find([10, 20, 30], 0))
#---> None
print(find(["hi", "there", "you", "there"], 'there'))
#---> 1

CodePudding user response：

Here is a example Not the function is 'seeded' with a value of -1 for count, which is then updated with each recursion.

def first_index_recursive(l: list, item, count = -1) -> int:
    """
    return the index of the first element of the list that
    matches the item. If no match, return -1

    >>> first_index_recursive([34, 43, 3, 78, 1], 3)
    2
    >>> first_index_recursive([34, 43, 3, 78, 1], 99)
    -1
    >>> first_index_recursive([34], 34)
    0
    >>> first_index_recursive([], 99)
    -1
    >>> first_index_recursive([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14], 14)
    14
    """
    # original list was empty, or we didn't find it
    if len(l) < 1:
        return -1

    # each time we recurse, count increases by 1 and points to the current
    # index of the original list
    count  = 1

    # found it
    if l.pop(0) == item:
        return count
    # did not find it yet. recurse.
    return first_index_recursive(l, item, count)

# for testing of function
if __name__ == "__main__":
    import doctest
    doctest.testmod()