Using recursion to determine the index path of a nested function

user_13699071 0
Viewed 32

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.

recursion python
4 Answers

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

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

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
user_68909120

The accepted answer already explains how to fix your recursive function.

Note that an iterative function works just as well:

def iterative_index(xs, index_path):
   for idx in index_path:
       xs = xs[idx]
   return xs

Or using reduce:

from functools import reduce

def reduce_index(xs, index_path):
    return reduce(list.__getitem__, index_path, xs)

Testing:

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

print( iterative_index(xs, index_path) )
# 6

print( reduce_index(xs, index_path) )
# 6
user_30807230
Related