Recursion in Practice

The below function takes in a "root" folder as an argument. You may assume that:

• The context of this function is a normal file system (like the one you use to store files on your computer): folders contain files and/or other folders, which themselves contain files and/or other folders, etc. A folder cannot contain itself.
• The helper functions it calls are all defined, and all do what their names indicate they do.

# Recursive Function
def do_something(root):
    files = get_files_in_folder(root)
    folders = get_folders_in_folder(root)

    for file in files:
        rename(file)

    for folder in folders:
        do_something(folder)

Which is a valid description of what this function does?

-- Renames all the files in the input folder, and also all the files in any folders (or subfolders, subsubfolders, etc.) within that folder. Enters infinite recursion by calling itself for every folder. Renames all the folders (or subfolders, subsubfolders, etc.) within the input folder. Renames all the files in the input folder (and nothing else).

Loading...

Recall that recursive functions can always be written iteratively, and vice versa.

Which of the below iterative functions is equivalent to the above recursive function?

-- function_a function_b function_c

Loading...

def function_a(root):
    files = get_files_in_folder(root)
    folders = get_folders_in_folder(root)

    for file in files:
        rename(file)

    for folder in folders:
        for file in get_files_in_folder(folder):
            rename(file)

def function_b(root):
    files = get_files_in_folder(root)
    folders = get_folders_in_folder(root)

    for file in files:
        rename(file)

    for folder in folders:
        for file in get_files_in_folder(folder):
            rename(file)
        for subfolder in get_folders_in_folder(folder):
            for file in get_files_in_folder(subfolder):
                rename(file)

For function_c, note that extend is a function on lists which adds all the elements in another list to the end of the original list. For example:

x = [1, 2, 3]
x.extend([4, 5, 6])
print(x) # x is now [1, 2, 3, 4, 5, 6]

def function_c(root):
    files_to_rename = get_files_in_folder(root)
    folders_to_explore = get_folders_in_folder(root)

    i = 0
    while i < len(folders_to_explore):
        folder = folders_to_explore[i]

        files_to_rename.extend(get_files_in_folder(folder))
        folders_to_explore.extend(get_folders_in_folder(folder))

        i += 1

    for file in files_to_rename:
        rename(file)

The Takeaway

You're new to recursion now, so this may or may not be the case for you, but many people find the above recursive function easier to understand and write than its iterative counterpart. This happens most often for problems of a particular sort: problems dealing with an inherently recursive structure. This example dealt with a file system. The file system on your computer is inherently recursive. You can think of it as a single root folder, containing files and other folders. But you can also think of each of those other folders as the root of its own file system, since each of them is just like the root: it has files and folders in it too. And, indeed, each of the folders within those folders can be thought of as its own file system root! If you encounter a problem with this type of structure (which happens perhaps most often with graph-like structures), and are finding it tedious or confusing to write an iterative approach, that's a great time to consider recursion.

The remainder of this week's exercises will not expect you to use recursion. The practice and written exercises will provide more practice with normal function writing, program design, and NumPy.

Next Exercise: Toll Lanes: Car Arrival Counting

Back to exercises