0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.