PowerShell Recursive Functions

A recursive function is a function that solves a problem by calling itself with smaller or modified input. Recursion is useful for tasks with a naturally repeating or hierarchical structure, such as mathematical sequences, tree/graph traversal, and nested folders.

Every recursive design requires two fundamental components: a base case that stops execution when a termination criterion is met, and a recursive case that narrows the problem space and makes the self-referencing call.

Anatomy of a Recursive Function

Whenever a function calls itself, PowerShell allocates a new stack frame in memory to track the state, parameters, and local variables for that specific invocation. If a function continues to call itself without a stopping condition, the call stack overflows, causing PowerShell to terminate execution with a call depth exception.

A functional recursive algorithm requires:

1. The base case is a conditional test at the beginning of the function that returns a concrete value without requiring another recursive call.
2. The recursive case involves logic that processes the current state, reduces the problem size, and then passes the updated input back into the function.

+-------------------------------------------------------+
| Function Call (Depth 0)                               |
|   Check Base Case -> False                            |
|   Invoke Function (Depth 1)                           |
|     Check Base Case -> False                          |
|     Invoke Function (Depth 2)                         |
|       Check Base Case -> True (Return value)          |
|     Process & Return value                            |
|   Process & Return final result                       |
+-------------------------------------------------------+

Basic Recursion: Function Calling Itself

In PowerShell, a function can call itself by name from within its own body, just like calling any other function.

function Show-Countdown {
    param(
        [int]$Number
    )

    Write-Host $Number

    if ($Number -gt 0) {
        Show-Countdown -Number ($Number - 1)
    }
}

Show-Countdown -Number 5

where:

• function Show-Countdown defines the function.
• Show-Countdown -Number ($Number - 1): the function calls itself with a decremented value.
• if ($Number -gt 0) controls when the recursive calls stop.

./basic-recursion.ps1

5
4
3
2
1
0

Base Case and Recursive Case Pattern

Every recursive function follows the same two-part structure:

• Base case: the stopping condition for recursion. Without it, the function would never terminate.
• Recursive case: the part of the function where it calls itself with a modified input, thereby progressing toward the base case.

function Get-Factorial {
    param(
        [int]$Number
    )

    if ($Number -le 1) {
        return 1   # Base case
    }

    return $Number * (Get-Factorial -Number ($Number - 1))   # Recursive case
}

Get-Factorial -Number 5

where:

• if ($Number -le 1) { return 1 } is the base case, stopping recursion once $Number reaches 1 or less.
• return $Number * (Get-Factorial -Number ($Number - 1)) is the recursive case, calling the function again with a smaller value.

120

Mathematical Recursion: Calculating Factorials

A classic implementation of recursion is calculating the factorial of a positive integer (n!). The mathematical definition is:

• n! = n × (n − 1)!

Base Case:

• 0! = 1
• 1! = 1

Implementing the Factorial Algorithm

The following script defines a recursive function that evaluates the factorial of an input integer with input validation.

function Get-Factorial {
    param (
        [ValidateRange(0, 20)]
        [int]$Number
    )

    if ($Number -le 1) {
        return 1
    }

    return $Number * (Get-Factorial -Number ($Number - 1))
}

$testNumbers = @(0, 1, 5, 7)

foreach ($num in $testNumbers) {
    $result = Get-Factorial -Number $num
    Write-Host "Factorial of $num = $result"
}

where:

• [ValidateRange(0, 20)] restricts inputs to values between 0 and 20 to prevent 64-bit integer overflows (System.Int64).
• if ($Number -le 1) is the base case. Stops recursion immediately when $Number reaches 1 or 0 and returns 1.
• Get-Factorial -Number ($Number - 1) is the recursive case. Calls itself while decrementing the input by 1.
• $Number * (...) multiplies the current number by the scalar output returned from the child stack frame once the base case unwinds.

./get-factorial.ps1

Factorial of 0 = 1
Factorial of 1 = 1
Factorial of 5 = 120
Factorial of 7 = 5040

Example: Directory Traversal

Recursion is a natural fit for traversing hierarchical structures like the file system. This example recursively lists every subfolder starting from a given path.

function Get-SubfoldersRecursively {
    param(
        [string]$Path,
        [int]$Depth = 0
    )

    $indent = "  " * $Depth
    Write-Host "$indent$Path"

    $subfolders = Get-ChildItem -Path $Path -Directory -ErrorAction SilentlyContinue

    foreach ($folder in $subfolders) {
        Get-SubfoldersRecursively -Path $folder.FullName -Depth ($Depth + 1)
    }
}

Get-SubfoldersRecursively -Path "C:\Projects"

where:

• Get-ChildItem -Path $Path -Directory retrieves immediate subfolders of the current path (the base data for each recursive step).
• foreach ($folder in $subfolders) { Get-SubfoldersRecursively ... } is the recursive case, calling the function again for each subfolder found.
• $Depth tracks how deep the recursion has gone, used purely for indentation in the output.
• The base case is implicit here: when Get-ChildItem returns no subfolders, the foreach loop simply doesn't execute, and the recursion naturally stops.

C:\Projects
  C:\Projects\ClientPortal
    C:\Projects\ClientPortal\Build
      C:\Projects\ClientPortal\Build\Output
    C:\Projects\ClientPortal\Docs
    C:\Projects\ClientPortal\Source
    C:\Projects\ClientPortal\Tests

Practical System Administration: Recursive Directory Traversal

While the Get-ChildItem -Recurse cmdlet handles flat and standard directory listings, writing a custom recursive directory traversal function is necessary when you need conditional hierarchy formatting, granular access permissions, or formatted tree structures.

Visualizing a Directory Tree Structure

The following script traverses a file system structure recursively and prints an indented visualization of nested directories and files.

function Show-DirectoryTree {
    param (
        [string]$Path,
        [int]$Depth = 0,
        [int]$MaxDepth = 3
    )

    if ($Depth -gt $MaxDepth) {
        return
    }

    if (-not (Test-Path -LiteralPath $Path -PathType Container)) {
        return
    }

    $indent = "  " * $Depth
    $currentFolder = Get-Item -LiteralPath $Path
    Write-Host "$indent[+] $($currentFolder.Name)" -ForegroundColor Cyan

    $subDirectories = Get-ChildItem -LiteralPath $Path -Directory -ErrorAction SilentlyContinue

    foreach ($dir in $subDirectories) {
        Show-DirectoryTree -Path $dir.FullName -Depth ($Depth + 1) -MaxDepth $MaxDepth
    }

    $files = Get-ChildItem -LiteralPath $Path -File -ErrorAction SilentlyContinue
    foreach ($file in $files) {
        Write-Host "$indent  - $($file.Name)" -ForegroundColor Gray
    }
}

Show-DirectoryTree -Path "C:\Deployments\App01" -MaxDepth 2

where:

• [int]$Depth = 0 tracks the current recursion tier to calculate indentation levels.
• [int]$MaxDepth = 3 is a safeguard parameter defining the maximum permitted traversal depth.
• if ($Depth -gt $MaxDepth) is the depth guard base case. Halts recursion if the scan depth exceeds the administrative threshold.
• $indent = " " * $Depth is string multiplier syntax that dynamically creates leading spaces proportional to the stack depth.
• Get-ChildItem -LiteralPath $Path -Directory scans for immediate child folders only.
• Show-DirectoryTree -Path $dir.FullName -Depth ($Depth + 1) ... is the recursive call. Executes the function on each nested subdirectory while incrementing $Depth.

./show-directorytree.ps1

[+] App01
  [+] bin
    - App01.dll
    - App01.exe
    - App01.runtimeconfig.json
  [+] config
    - appsettings.json
    - connectionStrings.xml
  - run.bat

Controlling Recursion Depth

PowerShell includes internal limits to protect against unbounded stack growth. If a recursive function enters an infinite loop, the engine raises an error when the nesting level becomes excessive.

function Invoke-InfiniteLoop {
    Invoke-InfiniteLoop
}

Invoke-InfiniteLoop

./infinite-recursion-demo.ps1

The script failed due to call depth overflow.
    + CategoryInfo          : InvalidOperation: (:) [], ScriptCallDepthException
    + FullyQualifiedErrorId : CallDepthOverflow

Practical Usage: When to Use Recursion

Recursion is a good fit when:

• The problem is naturally defined in terms of smaller versions of itself (factorials, Fibonacci sequences, tree/graph traversal).
• You're working with hierarchical data, such as folder structures, XML/JSON trees, or organizational charts.
• The recursion depth is reasonably bounded, to avoid stack overflow issues.

Key Takeaways

• Every recursive function needs a base case and a recursive case.
• The base case stops recursion; the recursive case moves the problem toward the base case.
• Recursion is powerful for hierarchical data, but it consumes stack space.
• Use an explicit depth limit or cycle detection when traversing file systems or graphs.
• Prefer iterative solutions when the problem does not naturally decompose into smaller copies of itself.