Walk folder tree without recursion c#

Question

How to change this recursive loop with non recursive? I know this method is easy way but i'm interested in non recursive way of this solution.

using System;
using System.IO;

namespace NonRecursion {
    class NonRecursion {
        static void Main() {
            string createPath = Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments);

            string getPath = createPath + @"\folder";
            GetDirsPath(getPath);

            Console.ReadKey();
        }

        static void GetDirsPath(string getPath) {
            string[] dirs = Directory.GetDirectories(getPath);

            for (int i = 0; i < dirs.Length; i++) {
                Console.WriteLine(dirs[i]);
                GetDirsPath(dirs[i]);
            }
        }
    }
}

Can i change only this function?

static void GetDirsPath(string getPath) {
            string[] dirs = Directory.GetDirectories(getPath);

            for (int i = 0; i < dirs.Length; i++) {
                Console.WriteLine(dirs[i]);
                GetDirsPath(dirs[i]);
            }
        }

Hint: You'll want to use a Queue<> or a Stack<> in `GetDirsPath` — Sean, Nov 29 '16 at 11:50
Is this an excercise or not? Because if this is not an excercise then you should look at the version of [GetDirectories](https://msdn.microsoft.com/en-us/library/ms143314(v=vs.110).aspx) that walks for you the subfolder tree and returns everything with a single call — Steve, Nov 29 '16 at 11:51
And you should choose queue and stack by the kind of traversal you need to do, whether it's breadth-first or depth-first. — Paul Stelian, Nov 29 '16 at 11:52
The theory says that any recursive method can be converted into a non-reciursive solution. — Thomas Weller, Nov 29 '16 at 11:53
Possible duplicate of [Can every recursion be converted into iteration?](http://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration) — Thomas Weller, Nov 29 '16 at 11:58
The recursive method is needed in this case. You are missing in your code an exception handler in case you don't have credentials to access a folder. The exception will cause the program to halt without completing. Using a recursive methods will allow the application to continue when a credential exception occurs. — jdweng, Nov 29 '16 at 12:13
@Mr.Pro I suggest adding more details to your question and what exactly you want. Usually general and unclear questions get general answers. Non-recursive approach would need some kind of stack. — Slai, Nov 29 '16 at 12:13

Matthew Watson · Accepted Answer · 2016-11-29T12:19:27.123

How about this:

public static IEnumerable<string> AllFolders(string root)
{
    var folders = new Stack<string>();
    folders.Push(root);

    while (folders.Count > 0)
    {
        string folder = folders.Pop();
        yield return folder;

        foreach (var item in Directory.EnumerateDirectories(folder))
            folders.Push(item);
    }
}

Test code (console app):

static void Main()
{
    foreach (var dir in AllFolders("<your root folder here>"))
    {
        Console.WriteLine(dir);
    }
}

Here's an alternative approach using a List<string>:

public static IEnumerable<string> AllFolders(string root)
{
    var folders = new List<string> {root};

    while (folders.Count > 0)
    {
        string folder = folders[folders.Count - 1];
        folders.RemoveAt(folders.Count-1);
        yield return folder;
        folders.AddRange(Directory.EnumerateDirectories(folder));
    }
}

These both work the same way:

They maintain a list (or stack) of directories that have not yet been output, starting with the root directory.

The algorithms remove the topmost (stack) or last (list) directory from the stack/list and output it. Then they add all the subdirectories of that directory to the list/stack and repeat, until the list/stack is empty.

In particular, note that the List<> version is in fact merely using a List<> as a Stack<>, so it's algorithmically identical.

If you just want to make minimal changes to the GetDirsPath() method:

static void GetDirsPath(string getPath)
{
    var dirs = new List<string> { getPath };

    while (dirs.Count > 0)
    {
        string dir = dirs[dirs.Count - 1];
        dirs.RemoveAt(dirs.Count - 1);
        Console.WriteLine(dir);
        dirs.AddRange(Directory.EnumerateDirectories(dir));
    }
}

"How about this" is similar to "try this" for me. I don't like "try this" answers, because I can try a lot, just for finding out that it does not work. Your answer differs very much from OPs answer, so it seems to me that you have not converted his recursive code into non-recursive, but re-written everything. — Thomas Weller, Nov 29 '16 at 12:03
@Mr.Pro Added a version with minimal changes to `GetDirsPath()`. — Matthew Watson, Nov 29 '16 at 12:11

score 2 · Answer 2 · answered Nov 29 '16 at 11:56

2

You can use GetDirectories method:

string getPath = createPath + @"\folder";

var allDirectories = Directory.GetDirectories(getPath, "*.*", System.IO.SearchOption.AllDirectories);

To get iterate through them:

foreach (string dir in allDirectories) 
{
    Console.WriteLine(dir);
}

https://msdn.microsoft.com/en-us/library/bb513869.aspx

answered Nov 29 '16 at 11:56

Yaser

5,609
1
15
27

1

I know this method but I only want to change GetDirPath function. – Mr.Pro Nov 29 '16 at 12:00

Walk folder tree without recursion c#

2 Answers2