Recursion

How your computer works out the size of a folder full of folders

Recursion means solving a problem by solving a smaller copy of the same problem, then using that answer. A recursive function is one that calls itself on the smaller copy.

Take a folder Photos with two files, 3 MB and 1 MB, and a subfolder Trip holding a 5 MB file. Its size is its own files plus each subfolder's size. Measuring Trip is the same job on a smaller folder, so the function calls itself.

Every recursion needs two parts. The base case is small enough to answer directly, like a folder with no subfolders. The recursive case splits the job into smaller copies: add up my files, then ask each subfolder.

Recursion

The -r in rm -r and cp -r stands for 'recursive'

On Linux and macOS, rm -r deletes a folder and everything inside it, and cp -r copies a whole folder tree. Without -r, rm refuses to delete a folder at all.

The -r tells the command to treat each subfolder as a smaller copy of the same job: handle its files, then its subfolders the same way. The folder size in Windows Properties or macOS Get Info adds up nested folders just like this.

Recursion

Each folder asks its subfolders, and the innermost answer at once

Recursion stops because each call works on a strictly smaller problem, so the calls must reach the base case. Then answers flow back: Trip returns 5, and the paused Photos call resumes and finishes with 9.

Paused calls wait on the call stack, a pile of memory notes recording where each call was and what it still had to add. The last call to start is the first to finish.

Without a reachable base case, calls pile up until stack space runs out, a crash called a stack overflow. Python stops at about 1,000 nested calls by default.