Not tail recursive

PowerShell supports recursion but not tail recursion. A simple test.

function simpleTest ($n)
{
    if($n -ne 0) { $n; simpleTest ($n-1) }
}

PS C:\> simpleTest 10
10
9
8
7
6
5
4
3
2
1

PS C:\> simpletest 99
99
98
97
96
95

The script failed due to call depth overflow. The call depth reached 101 and the maximum is 100.

Bruce Payette, co-designer of PowerShell, responds

Recursion depth limit is fixed in version 1. Deep recursion was causing problems in 64bit mode because of the way exceptions were being processed. It was causing cascading out-of-memory errors. The net result was that we hard-limited the recursion depth on all platforms to help ensure that scripts would be portable to all platforms.

So let’s get this to work by translating it to a ‘trampoline style’.

function simpleTest ($n)
{
  while ($true)
  {
      if($n -ne 0) { $n; $n-=1 }
      else {break}
   }
}

An upcoming post showing a parser, used tail recursion, quickly hit the call depth error, now it uses the trampoline loop.