Filesystem Traversal

Now that you’ve seen how recursion works, we can use it to solve certain problems that would otherwise be uncrackable.

One type of problem in which recursion is a natural fit is when we need to delve into multiple layers of a problem without knowing how many layers there are.

Take the example of traversing through a filesystem. Let’s say you have a script that does something with all the contents inside a directory, such as printing all the subdirectory names. However, you don’t want the script to only handle the immediate subdirectories—you want it to act on all the subdirectories within the subdirectories of the directory and all of their subdirectories, and so on.

Let’s create a simple script that prints the names of all subdirectories within a given directory:

	import os


	def print_subdirectories(directory_name):

	for filename in os.listdir(directory_name):
	if os.path.isdir(filename):
	path = os.path.join(directory_name, filename)
	print(path)

We can call this function by passing in a directory name. If we want to call it on the current directory, we could write the following:

print_subdirectories(".")

In this script, we look through each file within the given directory. If the file is itself a subdirectory, we print the subdirectory name.

While this works well, it only prints the names of the subdirectories immediately within the current directory. It doesn’t print the names of the subdirectories within those subdirectories.

Let’s update our script so that it can search one level deeper:

	import os


	def print_subdirectories(directory_name):

	for filename in os.listdir(directory_name):
	if os.path.isdir(filename):
	path = os.path.join(directory_name, filename)
	print(path)

	for filename2 in os.listdir(path):
	path2 = os.path.join(path, filename2)
	if os.path.isdir(path2):
	print(path2)

Now, every time our script discovers a directory, it then conducts an identical loop through the subdirectories of that directory and prints the names of the subdirectories. But this script also has its limitations because it’s only searching two levels deep. What if we want to search three, four, or five levels deep? We would need five levels of nested loops.

And what if we want to search as deep as our subdirectories go? That would seem to be impossible, as we don’t even know how many levels there are.

And this is where recursion really shines. With recursion, we can write a script that goes arbitrarily deep—and with a lot less code!

	import os


	def print_subdirectories(directory_name):
	for filename in os.listdir(directory_name):
	path = os.path.join(directory_name, filename)
	if os.path.isdir(path):
	print(path)
	print_subdirectories(path)

As this script encounters files that are themselves subdirectories, it calls the print_subdirectories method upon that very subdirectory. The script can therefore dig as deep as it needs to, leaving no subdirectory unturned.

To visualize how this algorithm acts on an example filesystem, examine this diagram, which specifies the order in which the script traverses the subdirectories.

/books/45079/OEBPS/recursively_recurse_with_recursion/filesystem.png

We’ll encounter this process again with a detailed visual walk-through in .