Course 3.2Lesson 5 of 5

Project: folders inside folders

In this project we walk through folders inside folders. A folder is a dictionary, and a file is a number that is its size, so a folder can hold folders to any depth. A loop cannot easily handle a depth that is not known, but a recursive function can: for each item, if it is a folder, ask the same question inside it, and if it is a file, use its size. We write functions for the total size, the number of files, a printed tree with indents, and a search that gives the path of a file. We plan the expected answers by hand, test the empty folder and a folder with only folders, and extend the project with the biggest file and the depth.

about 30 min1 simulation2 practice questions

Lesson 5 of 5Show all lessons

Try the code and the simulations beside the lesson.

What you will be able to do

After this lesson you can

recognise a structure that holds smaller copies of itself,
write recursive functions that walk through a nested dictionary,
use isinstance to tell a folder from a file, and
build a path while you go down.

The goal

On your computer, a folder can hold files and other folders, and those hold more files and folders, to any depth. You want to know the total size of a folder, how many files it holds, to show it as a tree, and to find a file by name. How deep the folders go is not known in advance. A loop alone cannot handle that. Recursion can.

Step 1: the data

A folder is a dictionary. Each key is a name. The value is either a number (a file, and the number is its size) or a dictionary (a folder inside).

The calls of factorial of 4. On the left, going down, each call waits for the next: factorial of 4 is 4 times factorial of 3, factorial of 3 is 3 times factorial of 2, factorial of 2 is 2 times factorial of 1, and factorial of 1 is 1, the base case. On the right, coming back up, the answers: factorial of 1 gives back 1, factorial of 2 gives back 2 times 1 which is 2, factorial of 3 gives back 3 times 2 which is 6, and factorial of 4 gives back 4 times 6 which is 24.

For example:

text

tree
  docs/        a.txt (10)    b.txt (20)
  pics/        x.png (300)   old/ -> y.png (50)
  readme.txt (5)

Work out the answers by hand.

The total size: 10 + 20 + 300 + 50 + 5 = 385.
The number of files: a.txt, b.txt, x.png, y.png, readme.txt, so 5.
The path of y.png: pics/old/y.png.

Step 2: the program

total_size(folder). The structure of a recursive function over a folder:

Go through the items of the folder.
If an item is a folder (a dictionary), the answer for it is the same function, called on it: total_size(item). This is the recursive call. We trust it to give the size of that folder.
If it is a file (a number), the answer is its size.
Add them all.

Where is the base case? It is hidden. A folder with no folders inside never makes a recursive call: the loop only meets files, and the function returns. So the calls stop by themselves when the folders run out. (An empty folder is the simplest case: the loop does not run, and the total is 0.)

isinstance(item, dict) asks whether item is a dictionary. It is a yes or no question about the type, and it is the way to tell a folder from a file here.

count_files(folder). The same shape. A file counts 1, a folder counts the files inside it.

show(folder, depth). It prints each name with two spaces of indent for each level. A folder prints its name with /, and then calls show on its content with depth + 1. The parameter depth is the extra information that grows as the calls go down. sorted(folder) puts the names in order.

find(folder, target, path). It builds the path as it goes down. Each call adds the name of the folder to path. When it finds the file, it returns the whole path. The important point is that a recursive call may find nothing (None), and then the loop must go on to the next item. Only an answer that is not None is returned at once.

Step 3: test the unusual cases

Test	Expected
an empty folder `{}`	size 0, 0 files
a folder with only a file	the size of the file, 1 file
a folder with only empty folders	size 0, 0 files
a folder five levels deep	the size of the one file at the bottom
a file name that appears twice	`find` gives the first one that it meets
a name that is not there	`None`

The third row is the true test of the base case: folders inside folders with nothing in them. The functions must return 0, and not stop with an error.

The function never needs to know how deep the tree goes. Each call handles one folder and trusts the calls inside it.

Step 4: extend it

Pick one or two, and do them without looking at a solution. Write the expected answers first.

The depth. How many levels deep is the tree? An empty folder has depth 1.
The biggest file. Find the name and the size of the biggest file.
The sizes of the folders. Print each folder with its total size.
All the paths. Make a list of the paths of all the files.
Find by size. Find all the files that are bigger than 100.

Common mistakes

Forgetting to add the recursive answer. total_size(item) on its own line does nothing. You must add the result to the total.
Using == to compare with a type. Use isinstance.
Returning too early in find. If the first folder does not hold the file, you must go on to the next. Return only when the answer is not None.
Forgetting that the depth grows with every call, and passing the old depth.
Changing the dictionary while you walk through it.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

Warm-up. Open the problem Look inside a record, from the dictionaries course, and compare it with this tree.
Build. Open the lab Project: folders inside folders. The checker uses a tree that is different from the example.
Stretch. Open the problem A list inside a list from the Puzzle Workshop, which has the same idea with lists.

Remember these

A structure that holds smaller copies of itself fits recursion: folders in folders.
For each item: if it is a folder, call the same function on it. If it is a file, use it.
The base case can be hidden: when no folders are left, the calls stop.
isinstance(item, dict) tells a folder from a file.
Build the path as you go down, and return only a real answer.