Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Calculating Fibonacci Numbers

Explore how to calculate Fibonacci numbers by understanding the classic recursive approach and its inefficiencies. Learn to analyze time complexity through recurrence relations, identify redundant calculations, and apply memoization to optimize the algorithm for better performance in C#.

We'll cover the following...

Classic recursive implementation of the Fibonacci series

Before we dive into what dynamic programming is, let’s have a look at a classic programming problem: the Fibonacci series. You’ve probably already seen it, but let’s start with a quick refresher. The Fibonacci series is a series of numbers in which each number is the sum of the preceding two numbers. The first two numbers are 0 and 1. So, it looks like 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Here is a C# method that returns the nthn^{th} Fibonacci number.

This is the Fibonacci golden spiral. The width of each square represents a Fibonacci number.

C#
using System;
class Program
{
    /// <summary>
    /// Finds the nth Fibonacci number.
    /// </summary>
    /// <param name="num">An integer number.</param>
    /// <returns>The nth Fibonacci number.</returns>
    public static int Fib(int num)
    {
        if (num <= 1)
        {
            return num;
        }
        return Fib(num - 1) + Fib(num - 2);
    }
    // Driver code to test above method
    public static void Main(string[] args)
    {
        var num = 6;
        Console.WriteLine(Fib(num)); // Output: 8
    }
}

Time complexity with recurrence relations

To calculate the time complexity of the code, we can solve a recurrence relation,

{T(0)=0,T(1)=1,T(n)=T(n−1)+T(n−2)+4\begin{cases} T(0) = 0, \\ T(1) = 1, \\ T(n) = T(n-1)+T(n-2)+4 \end{cases}

T(n)T(n) represents the Fib method. T(n−1)T(n-1) and T(n−2)T(n-2) represent the recursive calls to Fib(n-1) Fib(n-2), whereas the 44 represents the basic operations in the code. Namely, the comparison on line 12 and the two subtractions and one addition on line 17. Lastly, T(1)=1T(1) = 1 and T(0)=1 ...