时间戳

首页 > 解决方案 > 如果我将原始列表发送到更改它的递归函数，如何使用它？

python - 如果我将原始列表发送到更改它的递归函数，如何使用它？

问题描述

我有一个递归函数，它检查是否存在从列表的第一个对象到最后一个对象的路径。

step 是对象值，它可以向两个方向步进：

我从最后一个对象开始并检查哪个数字，如果我根据它的值从它迈出几步 - 转到最后一个。如果我设法以这种方式将最后一个链接到第一个，该函数应该返回 True。

在我的函数中，我在找到可以到达最后一个的数字后尝试更改列表，以便我找到的数字将是最后一个。然后我更改了数字，以便保存距离。

但是假设有一个数字可以进入它，之后我将如何检查该数字？我已经更改了列表..

假设我有这个列表： [6, 4, 8, 2, 4, 2, 3, 6] 该函数将返回 True。路径将是6,3,2,2,6

但该函数只接收一个列表。所以假设我从末尾开始，发现 2 到达列表的末尾。我该如何继续？如何检查哪个对象转到 2？（这次 - 2）等等？

    def walking_on_list(lst):
for i in range(len(lst)):
    if i + lst[i] == len(lst) - 1:
        if i == 0:
            return True
        else:
            diff = len(lst) - 1 - i
            lst[-1] = lst[i]
            lst[i] = 0
            for j in range(len(lst[:found])):
                lst[j] += diff
            temp = lst[found + 1:-1]
            temp = temp[::-1]
            for k in range(len(lst[found + 1:-1])):
                lst[k + len(lst[:found]) + 1] = temp[k]

            valid_path(lst)
    elif i == len(lst) - 1:
        return False

打印（walking_on_list（[6、4、8、2、4、2、3、6]）

标签： pythonrecursion

解决方案

使用不会更改列表的算法。

def walking_on_list(lst, indices=(0,)):
    index = indices[-1] + lst[indices[-1]]
    if index == len(lst) - 1:
        return True
    if (index < len(lst) and index not in indices
        and walking_on_list(lst, indices + (index,))):
        return True
    index = indices[-1] - lst[indices[-1]]
    if (index > 0 and index not in indices
        and walking_on_list(lst, indices + (index,))):
        return True
    return False

print(walking_on_list([6, 4, 8, 2, 4, 2, 3, 6]))

推荐阅读