A Better Recursion

by Jan 1, 2021

When a function calls itself, this is called “recursion”. You can see this technique often when a script wants to traverse part of the filesystem: a function processes folder content, and when it encounters a subfolder, it calls itself.

Recursion can be powerful but it’s very hard to debug and potentially dangerous because when you do a mistake, you end up in endless loops. Also, there is always the risk of a stack overflow when recursion depth is too high.

Many tasks that typically require recursion can also be designed by using a “queue”: when your code encounters a new task, instead of calling itself again, the new task is placed on the queue, and once the initial task is done, anything left on the queue is tackled.

Thanks to Lee Holmes, here is a simple sample that traverses the entire drive C:\ but does not use recursion. Instead, you can see the queue in action:

# get a new queue
[System.Collections.Queue]$queue = [System.Collections.Queue]::new()
# place the initial search path(s) into the queue
# add as many more search paths as you need
# they will eventually all be traversed

# while there are still elements in the queue...
    while ($queue.Count -gt 0)
        # get one item off the queue
        $currentDirectory = $queue.Dequeue()
            # find all subfolders and add them to the queue
            # a classic recurse approach would have called itself right here
            # this approach instead pushes the future tasks just onto
            # the queue for later use
            [IO.Directory]::GetDirectories($currentDirectory) | ForEach-Object {
        catch {}
            # find all files in this folder with the given extensions
            [IO.Directory]::GetFiles($currentDirectory, '*.psm1')
            [IO.Directory]::GetFiles($currentDirectory, '*.ps1')

Twitter This Tip! ReTweet this Tip!