回溯算法实现在特定路径下查找文件

回溯算法实现在特定路径下查找文件

题目描述：给定你一个路径，一个文件名。写脚本查找这个路径下（包括子目录）所有叫这个文件名的文件。

即，本文用Python实现

find path -name file_name

这个功能。

---

乍一看感觉挺简单的，一个递归就可以实现。实际上，得用回溯思想。请欣赏代码：

# author: muzhan
import os
import os.path as osp

def find(path, name, res=[]):
    ls = os.listdir(path)
    if name in ls:
        res.append(osp.join(path, name))
    for sth in ls:
        if osp.isdir(osp.join(path, sth)):
            find(osp.join(path, sth), name, res)
    return res


if __name__ == "__main__":
    current_path = './jsons/'
    name = 'apple.json'
    abs_path = find(current_path, name)
    print(abs_path)

解析：
首先要了解回溯的一般要领：
· 分支+递归；
· 合适的判断条件（减少分支）；
· 中间结果要伴随形参传递；