How to convert this recursive algorithm to an iterative form?

Question

Let us assume there's a folder structure as shown below: The letters a-d represent folders and the number 1-5 represent video files where for the file n, size(n)=n. So, 1 = 1MB, file 2 = 2MB, etc.

a
├── 1
├── b
│   ├── 2
│   └── 3
└── c
    ├── 4
    └── d
        └── 5

3 directories, 5 files

I want to write a script that takes as input a directory (e.g., a), and tells us the total video duration in that folder (iT=immediateTime) and the total video duration in that folder and all its sub-folders (tT=totalTime).

My pseudocode is:

function calcTime(dir)
{
    tT = iT = singleLevelCalcTime(dir);
    foreach(subdirectory in dir) {
        t+= calcTime(subdirectory);
    }
    echo iT;
    echo tT;
    return t;
}

Now, according to the Crunch-Turing thesis, essentially, every recursive function is mathematically proven to have an equivalent iterative version. My problem is I can't find any way to do this using just loops. I've read that explicit stacks (instead of the implicit ones generated by the nature of recursion) can solve this, but I can't figure out how.

For example, the first part of the algo is simple - iT can be calculated by the same method as in the original algorithm. Now, the program must enter each sub-directory and perform the same task again. However, without using recursion, I'd have to provide multiple levels of nested loops (unknown number of levels) to loop through each file/folder in each level. Please tell me where my approach is lacking. I can't really comprehend how to build an explicit stack that can solve this!

Answer 1

You have to perform a visit of the directory graph, such as a DFS. Since the graph you're dealing with is a tree, you can use a tree traversal instead, which is conceptually identical but should be easier to implement.

Just a pedantic note: you don't need the Church thesis to say that every recursive function is Turing-computable, it can be proven formally.