Card 06/ 08
Recursive and Explicit-Stack Folder Counts in Python, Java and TypeScript
The same count written recursively and as a loop over a stack you manage.
Any recursion can be rewritten as a loop that keeps its own stack, a list of the work still to do, in place of the call stack, the stack of frames the language keeps for unfinished calls. This card covers that rewrite for counting the files under a folder, in Python, Java and TypeScript, and why it matters once the depth of the calls can reach many thousands.
Each listing holds three functions. The recursive count adds a folder's own files to the count for each folder inside it. The second walks down to the innermost folder and returns how deep it is; its recursive call is a tail call, meaning the last thing the function does, with nothing left to do in its frame once the call returns. The third is the loop: it keeps a list of folders found but not yet opened, and on each turn it takes one off the top, adds its files to the total, and puts the folders inside it on the list. The work the call stack did, remembering what is left, now lives in a list in ordinary memory, which can hold millions of entries.
All three run on a chain of 1,000,000 folders, each holding one file and the next folder, so the answer is 1,000,000 files at a depth of 1,000,000. Each listing was run, and the highlighted lines are the recursive calls and the loop's push.
Three folder walks on a chain 1,000,000 folders deep, in each language
class Folder:
def __init__(self, files, folders):
self.files = files
self.folders = folders
def count_files(folder):
return len(folder.files) + sum(count_files(inner) for inner in folder.folders)
def depth_of(folder, depth=1):
if not folder.folders:
return depth
return depth_of(folder.folders[0], depth + 1)
def count_files_with_stack(root):
total = 0
pending = [root]
while pending:
folder = pending.pop()
total += len(folder.files)
pending.extend(folder.folders)
return total
deepest = Folder(["notes.txt"], [])
for _ in range(999_999):
deepest = Folder(["notes.txt"], [deepest])
for name, count in (("count_files", count_files), ("depth_of", depth_of)):
try:
print(name, count(deepest))
except RecursionError as error:
print(name, "raised", type(error).__name__)
print("count_files_with_stack", count_files_with_stack(deepest))count_files raised RecursionError
depth_of raised RecursionError
count_files_with_stack 1000000import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
public class FolderCounts {
record Folder(List<String> files, List<Folder> folders) {}
static int countFiles(Folder folder) {
int total = folder.files().size();
for (Folder inner : folder.folders()) {
total += countFiles(inner);
}
return total;
}
static int depthOf(Folder folder, int depth) {
if (folder.folders().isEmpty()) {
return depth;
}
return depthOf(folder.folders().get(0), depth + 1);
}
static int countFilesWithStack(Folder root) {
int total = 0;
Deque<Folder> pending = new ArrayDeque<>();
pending.push(root);
while (!pending.isEmpty()) {
Folder folder = pending.pop();
total += folder.files().size();
folder.folders().forEach(pending::push);
}
return total;
}
public static void main(String[] args) {
Folder deepest = new Folder(List.of("notes.txt"), List.of());
for (int i = 0; i < 999_999; i++) {
deepest = new Folder(List.of("notes.txt"), List.of(deepest));
}
try {
System.out.println("countFiles " + countFiles(deepest));
} catch (StackOverflowError error) {
System.out.println("countFiles threw " + error.getClass().getSimpleName());
}
try {
System.out.println("depthOf " + depthOf(deepest, 1));
} catch (StackOverflowError error) {
System.out.println("depthOf threw " + error.getClass().getSimpleName());
}
System.out.println("countFilesWithStack " + countFilesWithStack(deepest));
}
}countFiles threw StackOverflowError
depthOf threw StackOverflowError
countFilesWithStack 1000000type Folder = { files: string[]; folders: Folder[] };
function countFiles(folder: Folder): number {
let total = folder.files.length;
for (const inner of folder.folders) {
total += countFiles(inner);
}
return total;
}
function depthOf(folder: Folder, depth = 1): number {
if (folder.folders.length === 0) {
return depth;
}
return depthOf(folder.folders[0], depth + 1);
}
function countFilesWithStack(root: Folder): number {
let total = 0;
const pending: Folder[] = [root];
while (pending.length > 0) {
const folder = pending.pop()!;
total += folder.files.length;
pending.push(...folder.folders);
}
return total;
}
let deepest: Folder = { files: ["notes.txt"], folders: [] };
for (let i = 0; i < 999_999; i++) {
deepest = { files: ["notes.txt"], folders: [deepest] };
}
for (const [name, count] of [["countFiles", countFiles], ["depthOf", depthOf]] as const) {
try {
console.log(name, count(deepest));
} catch (error) {
console.log(name, "threw", (error as Error).name);
}
}
console.log("countFilesWithStack", countFilesWithStack(deepest));countFiles threw RangeError
depthOf threw RangeError
countFilesWithStack 1000000Both recursive functions failed in every language, and the loop counted every file. Python stopped at its limit of 1000 frames with a RecursionError, Java's main thread ran out of stack with a StackOverflowError, and Node raised a RangeError.
The tail call failed too, which surprises readers who know languages that reuse a frame for a tail call, so that such a recursion runs at any depth. None of these three does. CPython, the standard Python, keeps every frame on purpose, Java's virtual machine keeps them, and Node's engine keeps them, so a tail call is as deep as any other call.
The loop visits folders in a different order from the recursion, because it takes the last folder it pushed first. A count does not care about order; when the order matters, push a folder's contents in reverse so that the first comes off the stack first. Time is O(n) for n folders in either form. Choose the loop when the depth grows with the input, as it does down a chain or a list nested inside itself, and recursion when the depth stays small, where it reads as the definition.
← → move through sections and cards