Using recursion to determine the index path of a nested function-CodePudding

Im trying to make a function which finds a value from a list (xs) using another list (index_list) as an index path.

My function should work like this:

xs = [[[1, 2], 3], [4, 5, [6, 7]], 8, [9, 10, 11]]

>>> recursive_index(xs, [1, 2, 0])
6

So far I have:

def recursive_index(xs: List, index_path):

    if not index_path:
        return 0
    
    return recursive_index(xs, index_path[1:])

This however just returns 0 for everything, but I don't know what else the base case should be.

CodePudding user response：

You want this:

def recursive_index(xs, index_path):

    if not index_path:
        # if path is exhausted just return current element
        return xs

    # use first index on current list and recurse with the remaining path
    return recursive_index(xs[index_path[0]], index_path[1:])

CodePudding user response：

You're quite close, but you forgot that at each recursion you actually need to index the list so that you get further in at each recursion. This way, by the time you get to the base case, the variable xs will store the correct result and you can just return it.

This is what the code would look like:

def recursive_index(xs: List, index_path):
    if not index_path:
        return xs
    return recursive_index(xs[index_path[0]], index_path[1:])

CodePudding user response：

Your recursive function should keep extracting the value from xs at the first index of index_path until there is no more index in the rest of the path:

def recursive_index(xs, index_path):
    index, *rest = index_path
    value = xs[index]
    return recursive_index(value, rest) if rest else value