C# Fibonacci Sequence

Fibonacci numbers form a fascinating sequence. This sequence models and predict aspects of financial markets and natural phenomena. One way you can compute Fibonacci numbers is with recursion, but this can be slow. It is also possible to use iteration.

This C# program computes Fibonacci numbers with an iterative algorithm.

Program

Conceptually, the iterative Fibonacci method stores the result of the previous Fibonacci number before computing the next one. This reduces the time required quite a lot. To compute a Fibonacci number at a certain position N, we have to loop through all previous numbers starting at position 0.

Program that computes Fibonacci iteratively [C#]

using System;

class Program
{
    public static int Fibonacci(int n)
    {
	int a = 0;
	int b = 1;
	// In N steps compute Fibonacci sequence iteratively.
	for (int i = 0; i < n; i++)
	{
	    int temp = a;
	    a = b;
	    b = temp + b;
	}
	return a;
    }

    static void Main()
    {
	for (int i = 0; i < 15; i++)
	{
	    Console.WriteLine(Fibonacci(i));
	}
    }
}

Output

1
1
2
3
5
8
13
21
34
55
89
144
233
377

Note. If you just want to list Fibonacci numbers, you could change Fibonacci() to simply use Console.WriteLine(a). This would make the method print out each number as it is computed, which would reduce the total amount of computation required. The time spent printing to the Console would dominate the program's runtime.

Overflow

One problem with the implementation in this article is that the int types will overflow past the 47th Fibonacci number. To solve this problem, you can use the double type. Change Fibonacci() to return double. Additionally, change a, b, and temp to be of type double.

Summary

Fibonacci numbers don't just reveal some interesting aspects of the world; they also teach us about computer programming. By storing the previous value in a loop iteration, we avoid a tremendous amount of computational work. In the rare cases where Fibonacci numbers are critical, an iterative solution improves software dramatically.