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.
4 Comments
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/
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
}
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 }
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
sizealready, but let’s go with that, for the sake of equal comparisons):Ruby
PowerShell
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):
See also Recursion in PowerShell … Slow