How does this pseudocode for Tree traversals work?
My algorithms textbook has a pseudocode implementation of how to list the names of all the files in a tree directory. Let's say you have this tree directory right here. Does the pseudocode below know to print the names of the three files in the first child folder and then print the three items in the second folder, or does the code have to be called once for each path?
ParentFolder
ChildFolder1 - ChildFolder2
file1,file2,file3 - file4,file5,file6
ParentFolder
ChildFolder1 - ChildFolder2
file1,file2,file3 - file4,file5,file6
private void listAll( int depth )
{
printName( depth ); // Print the name of the object
if( isDirectory( ) )
for each file c in this directory (for each child)
c.listAll( depth + 1 );
}
public void listAll( )
{
listAll( 0 );
}
This is a recusive algorithm. Note that the function calls itself inside it. Assuming the print with depth prints the object name, functions calls itself over and over until it reaches a leaf node which is a file or directory with no directory in it
You know every recursive routine has a clear visible stopping criteria. This is where it should back track and return back to the function that called it. Here you have implicit criteria which is when the object not a directory. It is only calling itself when the current object is a directory. If the sub directory has another directory, then the function again calls itself for each of the sub directory and so on.
Oh ok, I think I see it now. When you said back track I was wondering how it back tracks. Usually when I think of "back track" I think of nested loops. But this program does have nested loops in a sense, because the recursion in line 6 takes place within a loop, and then it invokes a method that contains a loop. Am I visualizing it correctly?
Back tracking here would mean the following:
For the sake of simplicity suppose we have the following structure. Capitals (upper case) is directory, lowercase for file.
A->B->C->D->e
listAll(0) is called. -- instance 1 of listAll
prints A
calls itself for B
listAll(1) -- instance 2 of listAll
again there is only one directory
prints B
there is a directory C
listAll(2) is called -- instance 3 of listAll
prints C
there is only one directory no file
listAll(3) is called -- instance 4 of listAll
prints D
then there is an object, e
print e
there is no directory so it cannot enter the if part
BACK TRACKING
listAll(3) function returns to listAll(2) which had called it.
It has no more objects and nothing more to do so it back tracks again.
Function returns to the calling function listAll(1)
It has nothing more to do
It returns to calling function listAll(0)
It just returns.
For the sake of simplicity suppose we have the following structure. Capitals (upper case) is directory, lowercase for file.
A->B->C->D->e
listAll(0) is called. -- instance 1 of listAll
prints A
calls itself for B
listAll(1) -- instance 2 of listAll
again there is only one directory
prints B
there is a directory C
listAll(2) is called -- instance 3 of listAll
prints C
there is only one directory no file
listAll(3) is called -- instance 4 of listAll
prints D
then there is an object, e
print e
there is no directory so it cannot enter the if part
BACK TRACKING
listAll(3) function returns to listAll(2) which had called it.
It has no more objects and nothing more to do so it back tracks again.
Function returns to the calling function listAll(1)
It has nothing more to do
It returns to calling function listAll(0)
It just returns.
I think you explain "it just returns" in terms of "there is nothing left to do", but that doesn't explain what exactly it returns to. It helps when I visualize it as if it were a case of nested for loops. For example, in this code right here the inner loop prints 10 stars and then back tracks to the outer loop once it is done, and a new row begins. I know this isn't exactly what is happening in the recursive algorithm, but the "baton" is being passed back in the same way to the outer loop on line 5. Am I making sense?
for(i = 0, i < 10, i++){
for(k = 0, k < 10, k++)
System.out.print("*");
System.out.println("");
}
for(i = 0, i < 10, i++){
for(k = 0, k < 10, k++)
System.out.print("*");
System.out.println("");
}
Premium Content
You need an Expert Office subscription to comment.Start Free Trial