Recursion in PowerShell

Dealing with complex datasets may seem difficult in PowerShell. These datasets have unpredictable structures and can't be parsed easily. This the case when you need to extract all the member of an Active Directory group where member can be users and also groups that contains user and groups …. It's also the case with data coming from web services and API.

How to deal with these datasets with no fixed structure in PowerShell?

If you think a PowerShell script as a sequential series of instruction it's difficult. To solve this problem, you have to apply a programming design pattern called Recursion.

To be short, Recursion is a function calling itself. After all, when a function definition is loaded in memory it's available everywhere including inside the function.

Let's take a short example.

$object1 = @{
    "a" = 1 
    "b" =4    
    "c" = 2 
}

This simple, if I want to add all the value here all I have to do is to enumerate the value, like this

$a = 0    

ForEach($item in $Object1.GetEnumerator()) { 
    $a += $item.value 
} 

$a 

We can start by creating a function to handle the dataset

Function add-ObjectValue {
    [CmdletBinding()]
    Param(
        [Parameter(Mandatory, ValueFromPipeline)]
        [ValidateNotNullOrEmpty()]
        [object] 
        $Object
    )


        $count = 0 
        ForEach($item in $Object.GetEnumerator()) { 

                $count += $item.value 

        } 
        return $count

}

$object1 | add-ObjectValue 

It will return 7

But what happens if something changes in the dataset?

$Object2 = @{
        "a" = 1 
        "b" = @{ 
                a1 = 1
                a2 = 3
        }
        "c" = 2
}

$object2 | add-ObjectValue 

we get an error

Method invocation failed because [System.Collections.Hashtable] does not contain a method named 'op_Addition'. 

+             $count += $item.value 

+             ~~~~~~~~~~~~~~~~~~~~~ 

+ CategoryInfo          : InvalidOperation: (op_Addition:String) [], RuntimeException 

You can't add an integer to another object type.

Let's try something else

Function add-ObjectValue {
    [CmdletBinding()]
    Param(
        [Parameter(Mandatory, ValueFromPipeline)]
        [ValidateNotNullOrEmpty()]
        [object] 
        $Object
    )

    if ($Object.getType().Name -eq "Hashtable") {
        $count = 0 
        ForEach($item in $Object.GetEnumerator()) { 

                $count += $item.value 

        } 
        return $count
    }
}

No more error now, but it doesn't add all numbers. This is the moment to introduce recursion in the function.

Basically, recursion is a function calling itself. The goal of the function is to add numbers from hashtables. For every hashtable fund in the dataset, we need to return the sum of its numbers.

Function add-ObjectValue {
    [CmdletBinding()]
    Param(
        [Parameter(Mandatory, ValueFromPipeline)]
        [ValidateNotNullOrEmpty()]
        [object] 
        $Object
    )

    if ($Object.getType().Name -eq "Hashtable") {
        $count = 0 
        ForEach($item in $Object.GetEnumerator()) { 
            if ($item.value.getType().Name -eq "int32") {
                $count += $item.value 
            } 
            elseif ($item.value.getType().Name -eq "Hashtable") {
                $count +=  add-ObjectValue -Object $item.value
            }         
        } 
        return $count
    }
}

If the value found is a hashtable, the function will call itself to sum the hashtable numbers and return an integer. If the same hashtable contains another hashtable the function will also call itself to return an integer.

In other words, every hashtable will create its instance of the function to transform the hashtable into a sum.

It can work with far more complex datasets

$Object4 = @{
    "a" = 1 
    "b" = @{ 
            a1 = 1
            a2 = @{
                b1 = 3
                b2 = @{ 
                    c1 = 3
                    c2 = @{
                        d1=5
                    }
                }
            }
    }
    "c" = @{
        d1 = 1
        d2 = @{
            e1 = 1
            e2 = @{
                f1 =1
                f2 = @{
                    g1=1
                    g2 = @{
                        h1 = 1
                        h2 = @{
                            i1 = 1
                            i2 = 1
                        }
                    }
                }
            }
        }
    }
}

$object4 | add-ObjectValue
20

To be simple, recursion creates an instance of the function each time it finds a hashtable and returns an integer.

Recursion can be simple to implement. The difficult part for a non-programmer is to understand the concept and to recognize when you need to use it.

Recursion if perfect to deal with hierarchies represented in a tree structure. You can find it in objects like group members in active directory, vm representation, network segmentation, …

They all share a common pattern; a nested one to many relationships between objects.

Using recursion can save you time and are the most elegant solution to deal with this kind of dataset.