Enumerables, Yield and Fibonacci

I’ve been reading Vazirani’s Algorithms last night – quite an entertaining book considering the dry subject and similar books on the topic.  Vazirani’s website has a draft of the book as PDF too.

While the book is very much language-agnostic, I thought I’d have a crack at some of the algorithms using much newer semantics of C# and the yield keyword.

The Fibonacci sequence is especially interesting because it can be a  O(N2) recursive, or a O(N) linear performer depending on implementation.

I took a stab at the linear implementation, the results are surprisingly clean and simple.  In the first cut, I did the traditional loop thing with a conditional guard for iteration 0 and 1.  Second cut is much more elegant, removing the conditional guards all together and replacing them with a sequence of yields :

        foreach(UInt64 fibNumber in FibonacciSequence())
        {
            Console.WriteLine(fibNumber);
        }

        public static IEnumerable<UInt64> FibonacciSequence() 
        {
            UInt64 nminus1 = 1;
            UInt64 nminus2 = 0;
            UInt64 current = 1;

            yield return 0;
            yield return 1;
            while(true)
            {
                yield return current;
                nminus2 = nminus1;
                nminus1 = current;
                current = nminus2 + nminus1;
            }     
        }
Advertisements

About stephbu

Architect, Cyber-brickie, Father, Cook, Financier, Taxi Service
This entry was posted in Development. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s