CODEWITHSUNDEEP
pythonrecursion
Xxswagman1080noscopexX
Xxswagman1080noscopexX

Reputation: 15

Using recursion to determine the index path of a nested function

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.

Upvotes: 1

Views: 65

Answers (4)

Stef
Stef

Reputation: 15525

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

Upvotes: 0

Julien
Julien

Reputation: 15081

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

Upvotes: 1

blhsing
blhsing

Reputation: 106901

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

Upvotes: 0

Lecdi
Lecdi

Reputation: 2241

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

Upvotes: 1

Related Questions