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

Calculating Fibonnacci Numbers

Explore the calculation of Fibonacci numbers through classic recursion, understand the exponential time complexity via recurrence relations, and learn how dynamic programming techniques such as memoization reduce redundant computations to optimize performance.

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 Fibonacci Series. You have 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 ...

The Fibonacci Golden Spiral. The width of each square represents a Fibonacci number.
C++
#include <iostream>
using namespace std;
int fib(int i){
  if (i <= 1)
    return i;
  return fib(i - 1) + fib(i - 2);
}
int main(){
  int n = 6;
  cout << fib(n) << endl;
}

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} ...