在C#中递归列出文件和文件夹

Question

我编写此代码以递归方式列出c#中的文件和文件夹.

            var filesInTheCurrentDirectory = System.IO.Directory.GetFiles(rootFolder);
            if (!filesInTheCurrentDirectory.Any() && !System.IO.Directory.GetDirectories(rootFolder).ToList().Any())
            {
                return;
            }

            filesInTheCurrentDirectory.ToList().ForEach(file => System.IO.File.AppendAllText("e:\\personal\\tests.txt", System.IO.Path.GetFileName(file) + ":" + rootFolder + "\n"));
            System.IO.Directory.GetDirectories(rootFolder).ToList().ForEach(recursivePrintFolders);

虽然这很有用,但问题是:

1. 我正在使用递归.这是这样的best吗？(我尝试编写一个非递归函数,但因为我们事先并不知道每个文件夹的深度是多少).

2. 如何评估这个功能的性能？难道OlogN还是O(n)？(我很困惑,因为没有循环版本.根据我的说法,如果有两个for循环,我可以调用它O(n^2).)

任何想法或指导？

Answer 1

使用递归执行此操作的主要问题是:

1. 如果树的深度太大,则可能没有足够的堆栈空间.虽然拥有那么深的文件系统结构并不常见,但这并不是不可思议的.

2. 您使用的内存超出了所需的内存,因为您可以在堆栈框架中保留大量可能避免的数据.

至于渐近复杂度,你每个节点执行一个操作,无论它的大小如何,所以它是O(n),其中n是所有节点,而不是任何给定深度的节点.

但是,您可以使用内置方法遍历整个树,从而更有效地处理所有这些问题.它会比你提出的解决方案更有效,即使你的非递归,只需使用:

foreach(string file in Directory.EnumerateFiles(path, "*", 
    SearchOption.AllDirectories))
{
    System.IO.File.AppendAllText("e:\\personal\\tests.txt",
        System.IO.Path.GetFileName(file) + ":" + rootFolder + "\n")
}

虽然该解决方案可能不使用递归,但如果您想知道如何自己编写非递归树遍历,则可以使用如下通用方法:

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source
    , Func<T, IEnumerable<T>> childrenSelector)
{
    var stack = new Stack<T>(source);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childrenSelector(next))
            stack.Push(child);
    }
}

在你的情况下调用它可能看起来像这样:

var allFiles = new[] { new DirectoryInfo(path) }
    .Traverse(directory => directory.EnumerateDirectories())
    .Select(directory => directory.EnumerateFiles());

请注意,虽然这对于遍历不提供完整遍历的内置方式的树来说很好,但这通常不适合遍历文件系统.您应该使用第一个解决方案,因为它已经针对遍历文件系统的特殊情况进行了高度优化.