Recursive Folder Search

Recursive Folder Search

Recursion is a simple and effective technique for searching in a heirarchy.  This example shows how to access the folder heirarchy to list all files and folders.  It can be used as a pattern for any similar recursive procedure..

Recursion is a processing structure in which a routine calls itself.  It is used in solving problems where a process must be applied at multiple levels in a heirarchical structure.  The typical example is the calculation of a factorial.   The usual formula for the calculation of factorial N is
N! = N x N-1 x N-2 …. x 1
but this can be restated in recursive form as
N! = N x (N-1)!
1! = 1

Note that the calculation refers to itself, and that there is a terminating condition (1!).  Both these conditions are required in order to be able to implement a solution as a recursive procedure.

In this example – a recursive folder search – the routine will refer to itself by invoking a folder search for all folders within the current folder, and the terminating condition is that all folders in the currrent folder have been searched.

Create a form with a text box and a listbox.   Paste in the following code, and run the example.  Select a folder (eg, C:\Users\Public).   Note that some folders in the selected path may be inaccessible.

Imports System.IO
Public Class Form1

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MyBase.Load
  Dim FD As New FolderBrowserDialog
  If FD.ShowDialog <> Windows.Forms.DialogResult.Cancel Then
    TextBox1.Text = FD.SelectedPath
    ListBox1.Items.Add(TextBox1.Text)
    DirSearch(TextBox1.Text, 3)
  End If
End Sub

Sub DirSearch(ByVal sDir As String, ByVal Indent As Integer)
  Indent += 3
  Try
    For Each d As String In Directory.GetDirectories(sDir)
      ListBox1.Items.Add(Space(Indent) & d)
      DirSearch(d, Indent)
    Next
  Catch x As System.Exception
    ListBox1.Items.Add(Space(Indent) & "**" & x.Message & "**")
  End Try
  For Each f As String In Directory.GetFiles(sDir, "*.*")
    Dim FI As FileInfo = New FileInfo(f)
    ListBox1.Items.Add(Space(Indent) & FI.Name)
  Next
End Sub

End Class

The topmost folder name is added to the list box and the DirSearch sub is called with the topmost folder name and an indent of 3.  Firstly, the indent is increased by 3.  Then, for each folder in this topmost folder, the name of this sub folder is listed, then the DirSearch sub is called with the subfolder name and the new indent.  If this subfolder has subfolders, they are each processed in turn.  When the routine terminates (after possibly going down several more levels in the heirarchy) then the files in this subfolder are listed, then this routine terminates, the code continues for the processing of the next higher level folder, and so on until the files in the topmost folder are listed, and the processing stops.

The result is a listing of all files and folders underneath the topmost folder, with each subfolder being listed with its name, the subfolders it contains (wth their subfolders, etc) and the files it contains.  The listing is indented according to the depth of the folders.   It is important to note that the indent value is never decremented.   Each time the routine is called, indent is increased to ensure the subfolders are indented correctly.  When the routine returns, the value of indent to be used for the files in the current folder is the orginal value for that folder – the increase that occurred when the routine was called for the subfolders is forgotten when the routine finishes those subfolders and returns.  There is no need to decrement the indent, as the increment only occurs within that copy of the routine where it applies.

Note that a recursive procedure such as this can take a lot of memory – as each instance of the routine is invoked, the information about the status of the current routine needs to be stored in memory.  When the called routine terminates, the information about the routine that called it is restored, and processing continues.   This storage needs to occur for each level in the recursion heirarchy.   If there are many levels, the storage requirements might exceed the capacity of the machine.

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s