Recursion in Practice
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.
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)
Recall that recursive functions can always be written iteratively, and vice versa.
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