使用递归确定嵌套函数的索引路径

Question

我正在尝试创建一个函数，该函数使用另一个列表 (index_list) 作为索引路径从列表 (xs) 中查找值。

我的函数应该像这样工作：

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

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

到目前为止我有：

def recursive_index(xs: List, index_path):

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

然而这只是 returns 0 的一切，但我不知道基本情况应该是什么。

Answer 1

你想要这个：

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

Answer 2

您已经很接近了，但是您忘记了在每次递归时您实际上需要为列表编制索引，以便在每次递归时获得更多信息。这样，当您到达基本情况时，变量 xs 将存储正确的结果，您可以 return 它。

代码如下所示：

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

Answer 3

你的递归函数应该在 index_path 的第一个索引处继续从 xs 中提取值，直到路径的其余部分没有更多索引：

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

Answer 4

接受的答案已经解释了如何修复递归函数。

请注意，迭代函数同样有效：

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

或使用reduce:

from functools import reduce

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

测试：

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

使用递归确定嵌套函数的索引路径

Using recursion to determine the index path of a nested function

python

recursion