Browse: Home / Fibonacci Sequence … in PowerShell

Fibonacci Sequence … in PowerShell

By Joel 'Jaykul' Bennett on 31-Jan-2008

Scott Hanselman has been posting weekly snippets of code in various languages … today he did Fibonacci sequences … by the way, the point of his posts is to get you to read code in other languages, not necessarily showing the best way to do things in any of the languages represented — you only solve fibonacci sequences recursively in demos, not in real life. Well, except perhaps in tightly optimized tail-recursion languages, maybe in Haskell …

In C#


int fib(int x) { return (x<2) ? 1 :fib(x-1) + fib(x-2) }
fib(20);

In PowerShell


filter fib{ if($_-lt2){1}else{($_-1|fib)+($_-2|fib)}}
20 | fib

That’s just beautiful ;) ... incidentally, by default, PowerShell will only recurse up to 100 levels in the stack, so it kind-of sucks at recursive calls. You could also write that as a traditional function in powershell, but the way powershell passes arguments to functions makes it really awkward. I’ll put it on multiple lines so you can read it easier.


function fib($i){
  if($i -lt 2) {
    1
  }else{
    # yes, every one of these parentheses is required
    (fib ($i-1)) + (fib ($i-2))
  }
}

fib 20

As a side note, that function actually runs measurably slower than the pipeline method … but speeds up noticeably if you stick a few [int] type specifiers in the right places so PowerShell doesn’t have to infer types — something to think about.

Similar Posts:

Posted in | Tagged , , , | 4 Responses

4 responses to “Fibonacci Sequence … in PowerShell”

  1. Andy
    Andy 31-Jan-2008 at 10:55 am |

    I like the pipeline method. Very cool. You can also use double variable assignment.

    http://www.get-powershell.com/
    http://getpowershell.wordpress.com/2008/01/24/fibonacci-series-in-powershell/

  2. Jeffery Hicks
    Jeffery Hicks 31-Jan-2008 at 2:26 pm |

    This only gives you the last number in the sequence. Here’s a solution I came up with awhile ago (I’m very geeky for stuff like this) that uses recursion so you get the full sequence:

    Function Get-Fibonacci {
    Param([int]$n=0)

    if ($n -eq 0) {$result = 0}
    elseif ($n -eq 1) { $result =1}
    else {

    $result=(Get-Fibonacci($n-1)) + (Get-Fibonacci ($n-2))
    }

    write $result

    }

    for ($x=0;$x -le 11;$x++) {
    Get-Fibonacci $x
    }

  3. Jeffery Hicks
    Jeffery Hicks 31-Jan-2008 at 2:31 pm |

    I just found this mentioned on a related blog from Bruce’s book (I must have not gotten that far yet) which is even better. This will display the sequence up to 1000

    $c=$p=1; while ($c -lt 1000) { $c; $c,$p = ($c+$p), $c }

  4. Joel 'Jaykul' Bennett
    Joel 'Jaykul' Bennett 03-Feb-2008 at 12:35 am |

    Yeah, it’s true, I didn’t think of that when I read it at first, but the example that Hanselman gave in ruby is almost literally PowerShell, except it lacks dollar signs, and has those pesky extra words ;-) (not sure why his example for ruby assumes the target number is in a variable size already, but let’s go with that, for the sake of equal comparisons):

    Ruby
    x1,x2 = 0,1; 0.upto(size){puts x1; x1 += x2; x1,x2 = x2,x1}
     
    PowerShell
    $x1,$x2 = 0,1; 0..$size|%{$x1; $x1,$x2 = ($x1+$x2),$x1}
     

    Of course, although we all know that these solutions perform way better than the recursive algorithms, the only reason anyone bothers with fibonacci as an algorithm is to teach recursion, right? It’s a simple elegant recursive problem … and a great example of why recursion isn’t always the right answer, even when it’s elegant. :-|

    Oh, and just for the record, if you wanted to get the correct output to match the output of the “fib” function above, you’d need to change it just a tad (I think the Ruby solution is wrong too, but I don’t have an interpreter handy, and I’m in a hurry):

    $x1,$x2 = 0,1; 0..$size|%{$x1,$x2 = ($x1+$x2),$x1}; $x1
     

    See also Recursion in PowerShell … Slow