Skip to content

Dec 04: Searching a File System

Learning Objectives

After today's class, you should be able to:

  • Explain how the organization of a file system is recursive.
  • Explain the steps for writing a recursive function in Python.
  • Implement a recursive function that traverses a file system.

Reminders

Recursive Functions

How to write a recursive function:

  • Step 1. Base case: how will the recursion stop?
  • Step 2. Current case: what needs to be computed?
  • Step 3. Recursion: how will the arguments change?

Example Programs

Review and discuss examples 1–4 from Nov 27

File System Review

  • Folders contain files and other folders (which contain files and other folders …)
    • Everyday example of recursion!
  • Path to CS149 folder in the screenshot below: /home/mayfiecs/CS149
  • Path to selected file: /home/mayfiecs/CS149/PA3/.vscode/settings.json
    • Absolute path begins with a slash
    • Relative path: PA3/.vscode/settings.json

Screenshot of CS149 files

Using os and os.path

os – Miscellaneous operating system interfaces

  • os.getcwd() – get current working directory
  • os.listdir() – get list of directory entries

os.path – Common pathname manipulations

  • os.path.isfile(path) – True if regular file
  • os.path.basename(path) – get the filename
  • os.path.join(path, path2) – join two paths

Exercise 1: print_files

Implement a recursive function that prints a result: 

def print_files(path, indent=0):
    """Print all files reachable from the given path.

    Each level of the file system should be indented by four spaces.
    Print a colon after paths that represent a folder (directory).

    Args:
        path (str): The starting (current) location.
        indent (int): How many leading spaces to print.
    """


if __name__ == "__main__":
    print_files(os.getcwd())

Sample output when run on PA3 folder: 

PA3:
    .coverage
    .pytest_cache:
        .gitignore
        CACHEDIR.TAG
        README.md
        v:
            cache:
                lastfailed
                nodeids
                stepwise
    .vscode:
        settings.json
    __pycache__:
        catalog_utils.cpython-38.pyc
        schedule_utils.cpython-38.pyc
        test_catalog.cpython-38-pytest-7.4.3.pyc
        test_schedule.cpython-38-pytest-7.4.3.pyc
    buddy.py
    catalog_utils.py
    coverage.xml
    cs_catalog.json
    demo.py
    japn_catalog.json
    schedule_utils.py
    test_catalog.py
    test_schedule.py

Exercise 2: find_files

Implement a recursive function that returns a result:

def find_files(path, pattern):
    """Find all filenames containing the given pattern.

    Args:
        path (str): The starting (current) location.
        pattern (str): Characters in the filename.

    Returns:
        list: paths of files with pattern in the name
    """


if __name__ == "__main__":
    print(find_files(os.getcwd(), "cat"))

Sample output when run on PA3 folder: 

['PA3/__pycache__/catalog_utils.cpython-38.pyc',
'PA3/__pycache__/test_catalog.cpython-38-pytest-7.4.3.pyc',
'PA3/catalog_utils.py',
'PA3/cs_catalog.json',
'PA3/japn_catalog.json',
'PA3/test_catalog.py']