Understanding the Fibonacci Sequence: A Tutorial with C#

The Fibonacci sequence is one of the most famous and fascinating number sequences in mathematics. It appears in unexpected places, from the spiraling patterns of sunflower seeds to the genealogy of bees. In this tutorial, we'll explore what the Fibonacci sequence is, how it works, and how to implement it in C# using two different approaches.

What is the Fibonacci Sequence?

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones. The sequence usually starts with 0 and 1.

The sequence goes like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... and so on.

Here's how it's calculated:

• Start: 0, 1
• Next number: 0 + 1 = 1 -> Sequence: 0, 1, 1
• Next number: 1 + 1 = 2 -> Sequence: 0, 1, 1, 2
• Next number: 1 + 2 = 3 -> Sequence: 0, 1, 1, 2, 3
• Next number: 2 + 3 = 5 -> Sequence: 0, 1, 1, 2, 3, 5

This simple rule creates a pattern that grows exponentially.

Mathematically, this can be defined by the recurrence relation:

$F_n = F_{n-1} + F_{n-2}$

with seed values: $F_0 = 0$ $F_1 = 1$

Now, let's look at how we can generate these numbers using C#. We will explore two common methods: an iterative approach and a recursive approach.

Approach 1: The Iterative Method

The iterative approach uses a loop to calculate the numbers sequentially. It's generally the most efficient and practical way to generate Fibonacci numbers in production code because it avoids the overhead of repeated function calls.

Here is a C# function that takes an integer n and prints the Fibonacci sequence up to the n-th term.

using System;

public class FibonacciTutorial
{
    public static void Main(string[] args)
    {
        int n = 10; // Number of terms to generate
        Console.WriteLine($"Fibonacci sequence up to {n} terms (Iterative):");
        PrintFibonacciIterative(n);
    }

    public static void PrintFibonacciIterative(int n)
    {
        if (n <= 0) return;

        // Handle the first two terms separately
        int prev2 = 0; // F(i-2)
        if (n >= 1) Console.Write(prev2 + " ");
        
        int prev1 = 1; // F(i-1)
        if (n >= 2) Console.Write(prev1 + " ");

        // Start calculating from the 3rd term onwards
        for (int i = 2; i < n; i++)
        {
            int current = prev1 + prev2;
            Console.Write(current + " ");

            // Shift values for the next iteration
            prev2 = prev1;
            prev1 = current;
        }
        Console.WriteLine();
    }
}

How It Works

1. We initialize two variables, prev2 and prev1, with the first two numbers of the sequence (0 and 1).
2. We print these first two initial numbers.
3. A for loop starts from the third term (i = 2). Inside the loop, we calculate the current number by adding prev1 and prev2.
4. After printing the current number, we update prev2 to the value of prev1, and prev1 to the value of current. This effectively shifts our window of "the two preceding numbers" forward by one step for the next iteration.

Approach 2: The Recursive Method

The recursive approach is a more direct translation of the mathematical formula. A method calls itself to solve smaller instances of the same problem. While elegant, it can be very inefficient for larger values of n.

Let's see the C# implementation.

using System;

public class FibonacciTutorial
{
    public static void Main(string[] args)
    {
        int n = 10; // Number of terms to generate
        Console.WriteLine($"\nFibonacci sequence up to {n} terms (Recursive):");
        for (int i = 0; i < n; i++)
        {
            Console.Write(GetFibonacciRecursive(i) + " ");
        }
        Console.WriteLine();
    }

    // Function to get the n-th Fibonacci number recursively
    public static int GetFibonacciRecursive(int n)
    {
        // Base cases: F(0) = 0, F(1) = 1
        if (n <= 1)
        {
            return n;
        }
        // Recursive step: F(n) = F(n-1) + F(n-2)
        return GetFibonacciRecursive(n - 1) + GetFibonacciRecursive(n - 2);
    }
}

How It Works

1. The Main method has a loop that calls GetFibonacciRecursive(i) for each term from 0 to n-1.
2. The GetFibonacciRecursive function first checks for the base cases: if n is 0 or 1, it simply returns n.
3. For any other value of n, the function calls itself twice: once for n-1 and once for n-2, and returns the sum of their results.

The Problem with Recursion

Why is this method inefficient? To calculate a value like F(5), the function has to calculate F(4) and F(3). To calculate F(4), it must calculate F(3) and F(2). Notice that F(3) is calculated twice! As n gets larger, the number of redundant calculations grows exponentially.

This diagram visualizes the tree of function calls for calculating F(5). You can see how many times the same values are re-computed. This leads to a time complexity of O(2^n), which is very slow for large inputs, compared to the O(n) linear time complexity of the iterative approach.

Conclusion

You've now seen two ways to generate the Fibonacci sequence in C#. The iterative method is efficient and well-suited for most programming tasks. The recursive method, while mathematically clean, serves as a classic example of how direct recursion can sometimes lead to poor performance due to redundant work.

Happy coding!

Check out this video to see a step-by-step walkthrough of implementing the Fibonacci sequence in C# with Unity: How To Solve FIBONACCI SEQUENCE - UNITY C#.