Tuesday, August 12, 2008

Recursion in PowerShell

Recursion is one of those things that you'll probably find that you don't need to use all that often, but it's a really powerful concept, and where it's useful it can save you a lot of time, and not just in PowerShell.  Simply put, a recursive function has the ability to call itself, usually to perform a task with an unknown depth.

I remember the first time I hit this problem, and I had just started scripting.  I wanted to see who had permissions to a folder.  I walked the ACL on the folder and found a group, so wrote a function to grab the members of the group.  That's when I realized that some of the group's members were groups.  My first solution was horribly unwieldy.  I wrote a bunch of if/else statements that were able to grab group memberships up to three levels deep, and as I was looking unhappily at my hard-to-follow code, a spark of a memory started nagging at me, and I remembered an email thread about recursion, and that's the first time I really "got it".

Let's cut to the chase with an easy example: walking a directory tree.  The function below will use Get-ChildItem (dir) to grab all child items in the current PSPath and print their FullName.  In order to get all files in all child directories, every time it hits a directory it will call itself on the directory.  

# Recurse($path, $fileglob)
# Recurses through a psdrive and prints all items that match.
#
# Args:
#   [string]$path: The starting path
#   [string]$fileglob(optional): The search string for matching files
#
function Recurse ([string]$path, [string]$fileglob){
  if (-not (Test-Path $path)) {
    Write-Error "$path is an invalid path."
    return $false
  }

  $files = @(dir -Path $path -Include $fileglob)

  foreach ($file in $files) {
    if ($file.GetType().FullName -eq 'System.IO.FileInfo') {
      Write-Output $file.FullName
    }elseif ($file.GetType().FullName -eq 'System.IO.DirectoryInfo') {
      Recurse $file.FullName
    }
  }
}

In my mind I always picture a cat's cradle-style string looping through itself over and over until the final loop is met and a final tug unravels the whole thing back into a string.

12 comments:

tojo2000 said...

I've noticed that a few people find this post looking for how to recurse directories. I would actually suggest that you use the -Recurse option of Get-ChildItem rather than this function, in case that's what you're actually looking for.

tojo2000 said...

This seems to be a popular post. If you're looking for an example of a script that specifies how many levels deep to recurse, check out this one: http://tasteofpowershell.blogspot.com/2009/05/get-childitem-wrapper-that-lets-you-say.html

Anonymous said...

Get-ChildItem is not necessarily a better solution than this example - especially if you want to limit the depth of recursion. You see, Get-ChildItem does not leverage the filtering capability of the underlying filesystem - it fetches *ALL* the files and directories before filtering them locally in memory. Very, very inefficient for WAN links or large numbers of files...

tojo2000 said...

You are entirely correct. In fact, when efficiency is the most important thing, the best solution is often the least intuitive: Use New-Object to create a Scripting.FileSystemObject object, especially when you may be searching many levels of recursion.

brother.sand said...

Doesn't Get-ChildItem already have a -Recurse flag? It's there in the help page. There's even a shortcut of "dir -r".

tojo2000 said...

@brother.sand: Yes. This post was intended to be more about showing how a recursive function works than giving the best solution for walking a file tree.

Jonny said...

I know this is a 2 year old post but...

I came across it as I'm looking for a way of recursively walking through a Active Directory structure.

I already tried that method here as I figured it would (as it does in Java) but I'm having no joy.

Any way, nice post! :)

jv said...

This is a good basic demonstration of how to implement recursion however, it is not needed inPOwerShell as 'dir' does its own recursion.


Get-ChildItem c:\windows -recurse | Where-Object{$_.GetType() -eq [System.IO.FileInfo]} | select FullName

Same functionality but the recirs switch does it all for you.

The same technique works for AD with a provider.

woffi said...

What I want to do ist recurse through a directory tree and get the filesize and count for eacht subdirectory individually. In that case I think the -recurse option ist pretty useless, so this approach still has it benefits even for directories.

(Or is there any way to accompish this with "-recurse" that I'm not aware of? If so I'd be glad to learn about that!)

Zach said...

I just wrote recursive functions to remove items or indexes from powershell arrays.

I did for boring reasons, but they do demonstrate recursion doing something builtins can't.

function remove-item-list ($item,[array]$chckd_list=@(),[array]$list=(throw "the item $item was not in the list"))
{

if ($list.length -lt 1 ) { throw "the item $item was not in the list" }
$check_item,$temp_list=$list
if ($check_item -eq $item ) {
$chckd_list+=$temp_list
return $chckd_list
}
else {
$chckd_list+=$check_item
return (remove-item-list -item $item -chckd_list $chckd_list -list $temp_list )
}
}

function remove-index-list ([int]$count=0,[int]$index,[array]$chckd_list=@(),[array]$list)
{

if (($list.length+$count-1) -lt $index ) { throw "the index is out of range" }
$check_item,$temp_list=$list
if ($count -eq $index) {
$chckd_list+=$temp_list
return $chckd_list
}
else {
$chckd_list+=$check_item
return (remove-index-list -count ($count + 1) -index $index -chckd_list $chckd_list -list $temp_list )
}
}

mardukes said...

I don't share the sense that recursion is rarely needed. It is the FIRST choice for traversing a tree. When working with SharePoint you're never out of the trees. I needn't mention the file system.

Loïc SEBAS said...

Nice post.
It seems that the -Recurse switch doesn't work with PSSDRIVE so very good tip :)