Fibonacci Series : Recursion, Memoization, and Optimal Approach

The Fibonacci series is a popular mathematical sequence that appears in various fields, from computer science to nature. The sequence starts with two numbers, 0 and 1, and every subsequent number is the sum of the previous two numbers.

• F(0)=0,F(1)=1,
• F(n)=F(n−1)+F(n−2) for n≥2F(0) = 0

In this article, we will explore three different ways to compute the Fibonacci series in C#: using Recursion, memorization, and the Optimal Programming approach.

Fibonacci Using Recursion

The recursive approach is a simple and intuitive way to compute the Fibonacci sequence. However, it’s not the most efficient, as we’ll see in the complexity analysis.

public static int FibonacciRecursive(int n)
{
    if (n <= 1) return n; // Base case
    return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2); //Sub problem
}

Output

• The function FibonacciRecursive is called recursively for each value of n, reducing the problem size by computing the values for n-1 and n-2.
• For small values of n, this approach works fine, but for larger values, the number of recursive calls grows exponentially.
• Time Complexity: O(2^n) – Each function call branches into two additional calls, leading to an exponential growth in the number of calls.
• Space Complexity: O(n) – The maximum depth of the recursion stack is n, which defines the space complexity.

Fibonacci Using Memoization

Memoization is a technique that optimizes the recursive solution by storing previously computed results. This avoids the redundant calculations seen in the basic recursive approach.

public static int FibonacciMemoization(int n, Dictionary<int, int> memo = null)
{
    if (memo == null) memo = new Dictionary<int, int>(); //Used to store older results to avoid redundant recursion calls
    if (n <= 1) return n; //Base case   
    if (!memo.ContainsKey(n)) // check if already result is present. If not, then only compute
        memo[n] = FibonacciMemoization(n - 1, memo) + FibonacciMemoization(n - 2, memo); //Sub problem    
    return memo[n];
}

Output

 

• In this approach, we use a dictionary (or an array) to store previously computed Fibonacci numbers.
• If the function has already computed F(n), it retrieves the result from the dictionary instead of making recursive calls.
• Time Complexity: O(n) – Each Fibonacci number is computed only once and stored, avoiding the exponential calls. So, in this approach, we have reduced the time complexity to O(n) from O(2^n)
• Space Complexity: O(n) – We need additional space to store the results of the Fibonacci calculations in the dictionary, plus the recursion depth, which means space complexity is still the same as the previous approach.

Fibonacci Using an Optimal Approach

In this approach for Fibonacci, as we only need the last two Fibonacci values to calculate the next one so by storing just these two values (instead of the entire sequence), we iteratively compute the result in a loop. This reduces both time complexity to O(n) and space complexity to O(1).

public static int FibonacciOptimal(int n)
{
    if (n <= 1) return n;
    int prev1 = 0, prev2 = 1; //Variables to store last two results
    for (int i = 2; i <= n; i++)
    {
        int current = prev1 + prev2;
        prev1 = prev2;
        prev2 = current;
    }
    return prev2;
}

Output

• We initialize two variables, prev1 and prev2, representing the two previous Fibonacci numbers.
• As we iterate from 2 to n, we update these two variables to compute the current Fibonacci number.
• This approach avoids recursion entirely and uses a constant amount of space.
• Time Complexity: O(n) – We iterate once through the sequence up to n.
• Space Complexity: O(1) – Only a constant amount of space is needed, as we only store two variables at any given time. So, here we are able to reduce the space complexity of this approach to O(1) from O(n).

Comparing the Approaches

Let’s summarize the time and space complexities of the three approaches.

Implementation Approach	Time Complexity	Space Complexity
Recursion	O(2^n)	O(n)
Memoization	O(n)	O(n)
Optimal	O(n)	O(1)

Complete Code

using System;
using System.Collections.Generic;
namespace FibonacciSeries
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int n = 10; // calculate nth fibonnacci 
          
            Console.WriteLine("Fibonacci number using recursion for n = " + n + ":");
            Console.Write(FibonacciRecursive(n) + " "); 

            Console.WriteLine("\n\nFibonacci number using memoization for n = " + n + ":");
            Console.Write(FibonacciMemoization(n) + " ");  

            Console.WriteLine("\n\nFibonacci number using the optimal approach for n = " + n + ":");
            Console.Write(FibonacciOptimal(n) + " ");  
            Console.ReadLine();         
        }

        public static int FibonacciRecursive(int n)
        {
            if (n <= 1) return n;
            return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
        }

        public static int FibonacciMemoization(int n, Dictionary<int, int> memo = null)
        {
            if (memo == null) memo = new Dictionary<int, int>();
            if (n <= 1) return n;
            if (!memo.ContainsKey(n))
                memo[n] = FibonacciMemoization(n - 1, memo) + FibonacciMemoization(n - 2, memo);
            return memo[n];
        }

        public static int FibonacciOptimal(int n)
        {
            if (n <= 1) return n;
            int prev1 = 0, prev2 = 1;
            for (int i = 2; i <= n; i++)
            {
                int current = prev1 + prev2;
                prev1 = prev2;
                prev2 = current;
            }
            return prev2;
        }
    }   
}

Output