The Fibonacci Sequence in C#

Nov 23, 2023

c#, fibonacci, iteration, loop, recursion

The Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones.

Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted F_n .

Starting from 0 here are the first 20 numbers of the Fibonacci sequence.

F₀	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅	F₁₆	F₁₇	F₁₈	F₁₉
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

The Fibonacci Sequence

Mathematically we can describe this as:

xn= xn-1 + xn-2

The Fibonacci Sequence from Iteration

public int GetFibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }

    int current = 0;
    int next = 1;

    for (int i = 0; i < n; i++)
    {
        int temp = current;
        current = next;
        next += temp;
    }

    return current;
}

The GetFibonacci method uses Iteration to loop over the Fibonacci sequence until the Nth number is reached.

public List<int> GetFibonacciSequence(int length)
{
    var sequence = new List<int>();
    for (int i = 0; i < length; i++)
    {
        sequence.Add(GetFibonacci(i));
    }

    return sequence;
}

The GetFibonacciSequence method will use Iteration to loop over the length parameter, Adding the GetFibonacci int result to the List each cycle.

The Fibonacci Sequence from Recursion

public int GetFibonacci(int n)
{
    if (n <= 1)
    {
        return n;
    }

    return GetFibonacci(n - 1) + GetFibonacci(n - 2);
}

The GetFibonacci method uses recursion to recall the GetFibonacci method (itself), working down the Fibonacci sequence until the Nth number value reaches less than one, this is called a base condition.

If the recursion logic does not reduce towards a manner that converges on some condition, called a base condition, then an infinite recursion occurs. An infinite recursion can crash the system. Recursion terminates when a base condition is recognized.

public List<int> GetFibonacciSequence(int length)
{
    var sequence = new List<int>();

    return GetFibonacciSequence(length, sequence);
}

private List<int> GetFibonacciSequence(int length, List<int> sequence)
{
    if (length == sequence.Count)
    {
        return sequence;
    }

    sequence.Add(GetFibonacci(sequence.Count));

    return GetFibonacciSequence(length, sequence);
}

if (length == sequence.Count)
{
    return sequence;
}

Would be the base condition.

Difference between Recursion and Iteration

Recursion	Iteration
Recursion uses the selection structure.	Iteration uses the repetition structure.
Infinite recursion occurs if the step in recursion doesn’t reduce the problem to a smaller problem. It also becomes infinite recursion if it doesn’t convert on a specific condition. This specific condition is known as the base case.	An infinite loop occurs when the condition in the loop doesn’t become False ever.
The system crashes when infinite recursion is encountered.	Iteration uses the CPU cycles again and again when an infinite loop occurs.
Recursion terminates when the base case is met.	Iteration terminates when the condition in the loop fails.
Recursion is slower than iteration since it has the overhead of maintaining and updating the stack.	Iteration is quick in comparison to recursion. It doesn’t utilize the stack.
Recursion uses more memory in comparison to iteration.	Iteration uses less memory in comparison to recursion.
Recursion reduces the size of the code.	Iteration increases the size of the code.

table source

GitHub

I have put together a working example of the Fibonacci sequence in C# on GitHub here.