На этом шаге мы рассмотрим использование рекурсии, как альтарнативы стеку.

    Рекурсия - очевидная альтернатива итерации, когда программисту приходится явно отвечать за управление стеком или подобной ему структурой данных. Рассмотрим задачу поиска файла в файловой системе, которая состоит в том, чтобы по заданным именам файла f и начальной папки F напечатать все пути к файлам с именем f, находящимся в F или в любой из вложенных в неё папках. Например, рассмотрим файлы и папки на рисунке 1.

Рис.1. Пример дерева файловой системы

    Допустим, что файл file_paths.py содержит метод решения этой задачи. Тогда он, будучи вызванным с параметрами 'file01.txt' и начальной папкой '.' (на рисунке обозначена как 'initial_folder'), в которой находится file_paths.py, должен вывести что-то вроде:

.\file01.txt
.\folder01\folder03\file01.txt

    Поскольку файловая система имеет древовидную структуру, итерационному алгоритму придётся использовать структуру данных типа стек или очередь для поиска файла f в глубину или в ширину. В примере 10.3 приведена возможная реализация поиска в глубину с использованием стека.

import os


def print_path_file_iterative(file_name, folder):
    stack = []
    for entry in os.scandir(folder):
        if entry.is_file() and file_name == entry.name:
            print(entry.path)
        elif entry.is_dir():
            stack.append(entry)

    while len(stack) > 0:
        entry = stack.pop()
        for entry in os.scandir(entry.path):
            if entry.is_file() and file_name == entry.name:  
                print(entry.path)
            elif entry.is_dir():
                stack.append(entry)


print_path_file_iterative('file01.txt', '.')

    Сначала он подключает модуль os, чтобы воспользоваться методом os.scandir, который позволяет получить описание содержимого конкретной папки. В частности, он возвращает (неупорядоченное) множество объектов, находящихся в данной папке. Оно используется в цикле для проверки (по атрибуту name) имён файлов и папок в указанном пути, а также их свойств такими, например, методами, как is_file (является ли объект файлом) или is_dir (является ли объект папкой). Наконец, атрибут path используется для печати пути к найденному в файловой системе файлу.

    Определённый нами метод прежде всего объявляет пустой список, который будет представлять собой стековую структуру данных и содержать объекты-папки. После этого он используется в цикле для проверки всех файлов и папок в каталоге, заданном параметром folder. Для каждого объекта множества os.scandir алгоритм проверяет, является ли он файлом, и печатает его путь при совпадении его имени со значением параметра file_name. В противном случае процедура посредством метода is_dir определяет, является ли объект папкой. Если это так, то он помещает объект в стек (метод append). После чего алгоритм выполняет те же действия над объектами, находящимися в стеке. Этот процесс повторяется, пока стек не опустеет.

    На рисунке 2 приводится несколько состояний стека при выполнении кода из примера 10.3 для файлов и папок на рисунке 1.

Рис.2. Состояние стека при выполнении итерационного кода из примера 10.3 для файлов и папок на рисунке 1

    Сначала стек пуст (шаг 0). Затем в первом цикле алгоритма в стек помещаются два каталога, находящихся непосредственно в начальной папке (шаги 1 и 2), и печатается путь .\file01.txt. Потом метод переходит ко второму циклу (строки 11-17). Сначала он выталкивает каталог folder02 (шаг 3) и проверяет его. Так как он пуст, метод не печатает новых путей и добавляет новые подпапки в стек. На втором шаге цикла while процедура выталкивает folder01 (шаг 4). Эта папка содержит файл, но он не file01.txt. Однако, кроме него, она содержит подпапку, которая помещается на вершину стека (шаг 5). На следующем шаге цикла метод выталкивает folder03 (шаг 6), находит файл под названием file01.txt и печатает его полный путь. При этом он не добавляет новые объекты в стек, так как folder03 не содержит подкаталоги. Таким образом, стек становится пустым, и метод завершается. Вы можете проверить алгоритм на больших файловых системах, чтобы убедиться, что метод действительно выполняет поиск в глубину. В этом небольшом примере алгоритм начинает поиск файла с папки folder02. Если бы в ней были подпапки, то метод продолжил бы поиск в них, прежде чем искать в folder01.

    На следующем шаге мы закончим изучение этого вопроса.

Предыдущий шаг Содержание Следующий шаг