The Weekly Source Code 13 - Fibonacci Edition (original) (raw)
January 24, 2008 Comment on this post [135] Posted in ASP.NET | Microsoft | Programming | Source Code
If you're new to this, each week I post some snippets of particularly interesting (read: beautiful, ugly, clever, obscene) source and the project it came from. This started from a belief that reading source is as important (or more so) as writing it. We read computer books to become better programmers, but unless you're reading books like Programming Pearls, you ought to peruse some Open Source projects for inspiration.
And so, Dear Reader, I present to you the thirteenth in a infinite number of posts of "The Weekly Source Code." Here's some source I was reading this week. I wanted to see what a Fibonacci number generator looked like in a number of different languages.
Remember (from Wikipedia) that the Fibonacci sequence looks like this:
...after two starting values, each number is the sum of the two preceding numbers. The first Fibonacci numbers also denoted as Fn, for n = 0, 1, … , are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, ...
Here's a few implementations I thought contrasted nicely. There's also a great writeup on Fibonacci related things on Dustin Campbell's blog.
F#
- Here's a basic Fibonacci function in F#.
let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1) - Or, if you want input and output as an F# console application:
let fib_number = int_of_string (System.Environment.GetCommandLineArgs().GetValue(1).ToString());;
let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1);;
Printf.printf "\nThe Fibonacci value of %u is: %u\n" fib_number (fib fib_number);;
exit 0;;
Ruby
- Here it is in Ruby, from RubyTips.org:
x1,x2 = 0,1; 0.upto(size){puts x1; x1 += x2; x1,x2 = x2,x1} - But that's really hard to read and kind of smooshed onto one line. A more typical console app would look like this:
class FibonacciGenerator
def printFibo(size)
x1,x2 = 0, 1
0.upto(size){puts x1;x1+=x2; x1,x2= x2,x1} # note the swap for the next iteration
end
f = FibonacciGenerator.new
f.printFibo(10) # print first 10 fibo numbers
end
C#
- There's many ways to do this in C#, so let's start with a basic C# 2.0 implementation.
static int Fibonacci (int x)
{
if (x <= 1)
return 1;
return Fibonacci (x-1) + Fibonacci (x-2);
} - Now, here's a great way using C# 3.0 (actually, .NET 3.5 and System.Func from the new System.Core:
Func<INT , int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Scala
- Lots of folks are excited about Scala, and many are calling it "the latest programmer's shiny object." It's interesting not just for its syntax, but it's full interoperability with Java. Here's a recursive Fibonacci in Scala.
def fib( n: Int): Int = n match {
case 0 => 0
case 1 => 1
case _ => fib( n -1) + fib( n-2)
}
Erlang
- Here's Fibonacci in Erlang, and you can find many other implementations at LiteratePrograms.org, a great site for reading source!
fibo(0) -> 0 ;
fibo(1) -> 1 ;
fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .
Which is your favorite? I like the C# 3.0 one and the F# ones. Also the Ruby double variable swap is pretty cool. They just feel right, although a close runner-up is the LOLCode implementation of Fibonacci from a few weeks back.
About Scott
Scott Hanselman is a former professor, former Chief Architect in finance, now speaker, consultant, father, diabetic, and Microsoft employee. He is a failed stand-up comic, a cornrower, and a book author.
Hosting By