CODEWITHSUNDEEP
javarecursionioiteration
user1105826
user1105826

Reputation:

recursion to iteration

I am working in a desktop application for windows using Java. In my application, there is a requirement to search all .php. To do this, I use recursive methods.

import java.io.File;

public class Copier {

    public static void find(String source,String rep) {
        File src = new File(rep);
        if (src!= null && src.exists() && src.isDirectory()) {
            String[] tab = src.list();
            if (tab != null) {
                for(String s : tab) {
                    File srcc = new File(rep+"\\"+s);
                    if (srcc.isFile()) {  
                        if (srcc.getName().matches(".*"+source+"$")) {
                            System.out.println(s);
                        }
                    } else {
                        find(source,srcc.getAbsolutePath());
                    }
                }
            } else {
                //System.out.println(" list is null");
            }
        }
    }

    public static void main(String[] args) {
        try {
            find(".java", "C:\\");
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Is it possible to do this with an iterative algorithm?

Upvotes: 0

Views: 453

Answers (3)

Mason Bryant
Mason Bryant

Reputation: 1392

You can always use a queue in place of recursion. In this case, I think it makes the code look a little bit easier to read. Often you'll get better performance from an iterative implementation than a recursive one though in this case, they both run at nearly the same speed (at least on my machine).

public static List<String> find(final String source, final String directory)
{
    List<String> results = new LinkedList<String>();
    Stack<String> stack = new Stack<String>();

    stack.add(directory);

    String rep;
    while (!stack.isEmpty()) {
        rep = stack.pop();
        File src = new File(rep);
        if (src != null && src.exists() && src.isDirectory()) {
            String[] tab = src.list();
            if (tab != null) {
                for (String s : tab) {
                    File srcc = new File(rep + File.separatorChar + s);
                    if (srcc.isFile()) {
                        if (srcc.getName().matches(".*" + source + "$")) {
                            // System.out.println(s);
                            results.add(s);
                        }
                    } else {
                        stack.add(srcc.getAbsolutePath());
                    }
                }
            } else {
                // System.out.println(" list is null");
            }
        }
    }
    return results;
}

Upvotes: 1

Snicolas
Snicolas

Reputation: 38168

I can't see why you want to get rid of recursion although theoretically what you are looking for is possible.

But a good way to get a faster program could be to use a filefilter when you list the children of a directory. One for directories and one for matching files (this one should use a java.util.regexp.Pattern).

-updated

You can find the doc for the overload of File.list to use here. And for the pattern, you could something like a local variable (outside your loop or a data member if you use recursion).

 Pattern p = Pattern.compile( ".*"+source+".*" );
 boolean found = p.matcher( p.matcher( srcc.getName() ).matches() );

Oh, and by the way, don't convert srcc into a file ! Work with strings and build as few objects as you can.

Upvotes: 1

Petar Minchev
Petar Minchev

Reputation: 47393

Of course. Use breadth-first-search with queue. You start from C:\ and at every step you pop the top folder from the queue and push all subfolders to the end of the queue.

Pseudocode follows:

queue.push("C:\");
while (!queue.empty()) { 
   String topFolder = queue.pop();
   foreach (subFolder of topFolder) {
        queue.push(subFolder);
   }
}

Upvotes: 3

Related Questions