为什么我的递归函数返回一个空列表？

Question

我必须解决的问题是创建一个递归展平嵌套列表的函数。

下面是我的代码

我不明白的是程序如何不断返回一个空列表。我意识到我必须初始化一个空列表，这可能是这里的问题，但我还能如何解决这个问题？

def flat_list(nested_lst, low, high):
   new_lst = []

   if low >= high:
       return new_lst

   if type(nested_lst[low]) is list:
       for item in nested_lst[low]:
           new_lst.append(item)
       return flat_list(nested_lst, low+1, high)
    
   else:
       new_lst.append(nested_lst[low])
       return flat_list(nested_lst, low+1, high)


def main():
   lst = [[1], [[2, [3], 4], 5], 6]

   print(flat_list(lst, 0, len(lst)-1))


main()

Answer 1

我认为这个条款是您问题的典范：

   for item in nested_lst[low]:
       new_lst.append(item)
   return flat_list(nested_lst, low+1, high)

您将内容附加到 new_lst，然后在返回的结果中完全忽略它！

递归新手的典型问题是坚持在递归函数中间插入 for！关键是递归思考，相信递归来完成工作：

def flat_list(nested_lst):
    if nested_lst:
        head, *tail = nested_lst

        return (flat_list(head) if isinstance(head, list) else [head]) + flat_list(tail)

    return nested_lst

if __name__ == "__main__":
    lst = [[1], [[2, [3], 4], 5], 6]

    print(flat_list(lst))

你看到它可以在没有 low 和 high 的情况下完成，所以现在需要将它们添加回去，因为你需要使用它们。

that code that @RufusVS posted is to go inside the flattening function or does it go in the main function?

我个人会说，“两者都不是”。我将 @RufusVS 的代码包装在我的递归函数周围：

def flat_list(nested_list, low, high):

    def flat_list_recursive(nested_lst):
        if nested_lst:
            head, *tail = nested_lst

            head = flat_list_recursive(head) if isinstance(head, list) else [head]

            return head + flat_list_recursive(tail)

        return nested_lst

    new_list = list(nested_list) # shallow copy

    new_list[low:high] = flat_list_recursive(nested_list[low:high])

    return new_list
 
if __name__ == "__main__":
    lst = [[1], [[2, [3], 4], 5], 6]

    print(flat_list(lst, 1, 2))  # [[1], 2, 3, 4, 5, 6]

Answer 2

一个更具可读性的例子：

def flat_list(nested_lst):
   new_lst = []
   
   if type(nested_lst) is list:
       for item in nested_lst:
           new_lst += flat_list(item)
   else:
       new_lst.append(nested_lst)
       
   return new_lst

如果您追求 'purer' 递归函数，请删除 for 循环。就像：

def flat_list(nested_lst):
   if not nested_lst:
       return []
   
   head, *tail = nested_lst
   if type(head) is list:
      return flat_list(head) + flat_list(tail)
   else:
      return [head] + flat_list(tail)

Answer 3

可以通过执行以下操作强制使用 low 和 high 中的任何一个函数：

def flat_list(nested_list, low=None, high=None):   # arguments are optional
    if low is None:
        # put block contents of either no-arg answers in here
    else:
        nested_list[low:high]=flat_list(nested_list[low:high])
        return nested_list

为什么我的递归函数返回一个空列表？

Why is my recursive function returning an empty list?

python

recursion

nested-lists

python-3.x