Python递归DFS遍历嵌套列表打印完整路径问题

• 需求：基于深度优先搜索（DFS）递归实现嵌套列表的全路径打印，约定嵌套列表中索引为0的元素x[0]为父节点，索引1及之后的切片x[1:]为该父节点的子节点，最终输出所有从根节点出发到叶子节点的完整路径。
• 测试输入：

['1', ['2', ['3', ['4', ['5', ['6', ['7']], ['8', ['9']]]]]]]

• 嵌套结构可视化：

['1', 
    ['2', 
        ['3', 
            ['4', 
                ['5', 
                    ['6', 
                        ['7']
                    ], 
                    ['8', 
                        ['9']
                    ]
                ]
            ]
        ]
    ]
]

• 预期输出：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
1 -> 2 -> 3 -> 4 -> 5 -> 8 -> 9

• 原有代码实际错误输出：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
5 -> 8 -> 9

• 原有错误实现代码：

from typing import List
def __print(chains: List):
    """
    Assuming the input list where index 0 is the source, and index 1 is its
    children paths.
    """

    if (len(chains) == 0):
        return
    elif (len(chains) == 1):
        # reaching the end
        print("{0}".format(chains[0]))
        return
    else:
        # everything after index 0 is considered children
        children = chains[1:]

        # has children
        for child in children:
            print("{0} -> ".format(chains[0]), end='')
            __print(child)

原有实现采用递归过程中逐段打印内容的逻辑，没有维护从根节点到当前节点的完整路径状态：

1. 遍历第一个子分支（6->7）时，上层递归的1 -> 、2 -> 、3 -> 、4 -> 、5 -> 会按递归深度依次打印，最终拼接出正确的第一条路径。
2. 当递归回溯到节点5、遍历第二个子分支（8->9）时，上层1-4节点对应的打印语句已经执行完毕退出，不会再次触发，因此只会打印当前层的5 -> ，最终丢失所有上层路径前缀。

给递归函数增加路径累积参数，每进入一层节点就把当前父节点加入路径列表，遇到叶子节点时一次性拼接完整路径打印；递归遍历子节点时传递路径副本，避免不同分支的路径状态互相污染。

修正后可运行代码：

from typing import List

def print_paths(chains: List, current_path: List = None):
    # 初始化默认参数，规避Python可变默认值的共享陷阱
    if current_path is None:
        current_path = []
    
    if not chains:
        return
    
    # 将当前层父节点加入累积路径
    current_path.append(chains[0])
    
    if len(chains) == 1:
        # 到达叶子节点，拼接打印完整路径
        print(" -> ".join(current_path))
    else:
        children = chains[1:]
        for child in children:
            # 传递当前路径的副本，保证不同分支的路径状态独立
            print_paths(child, current_path.copy())


# 测试运行
test_input = ['1', ['2', ['3', ['4', ['5', ['6', ['7']], ['8', ['9']]]]]]]
print_paths(test_input)

运行后输出和预期完全一致：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
1 -> 2 -> 3 -> 4 -> 5 -> 8 -> 9

内容的提问来源于stack exchange，提问作者samxiao