Generate a Fibonacci sequence

Posted on  • tagged with 

The Fibonacci sequence is a series of numbers where each number in the sequence is the sum of the two preceding numbers, with the sequence beginning with 0 and 1. In mathematics, the Fibonacci numbers form the sequence, where numbers (n) are greater than 1 (n > 1).

To better understand how the fibonacci numbers are created in the sequence, view the below equation for generating any number in the fibonacci sequence.

Fn = Fn-1 + Fn-2

Generate the sequence

Now that the underlying mathematical equation is known, let's write an iterative solution that generates a vector<int> containing the fibonacci sequence.

#include <vector>
using namespace std;
// O(n) time and O(n) space
vector<int> fibonacciSequence(int n) {
if (n == 1) return {0};
if (n == 2) return {0,1};
vector<int> nums = {0,1};
for (int i = 2; i <= n; i++) {
nums.push_back(nums[i-1] + nums[i-2]);
}
return nums;
}

The above function fibonacciSequence accepts one parameter, the amount of fibonacci numbers to generate in the sequence and returns an array containing the fibonacci sequence from (0, n). For example, passing in n = 7 will generate the following sequence:

vector<int> sequence = fibonacciSequence(7);
int lastFib = sequence[7];
cout << "F(7) = " << lastFib << endl;
// F(7) = 13
for (auto num : sequence) {
cout << num << " ";
}
cout << endl;
// 0 1 1 2 3 5 8 13

Using a recursive approach to generate the sequence:

vector<int> fibonacciSeq(int n) {
if (n == 1) return {0};
if (n == 2) return {0,1};
vector<int> sequence = fibonacciSeq(n-1);
sequence.push_back(sequence[n-2] + sequence[n-3]);
return sequence;
}

Returning the Nth fibonacci number

To provide a more efficient algorithm. We can take a dynamic programming approach as this problem is easily broken into smaller subproblems. The recursive calls will be added to the recursion stack, which occupies O(n) space in memory as the depth of the tree will determine the number of recursive calls on the stack at a given time.

// recursive fibonacci sequence (without memoization)
// O(2^n) time and O(n) space
int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}

Using a tree to better visualize how the recursive calls are happening when we attempt to call fib(n), view the example below. At each root node, the algorithm requires two operations in order to compute the fib(n-1) and fib(n-2) values. That is, if there is n nodes in the tree, we will require 2^n operations to compute each root nodes left and right child node.

// 2^n operations
// for example fib(2) is computed twice and fib(1) and fib(3) computed thrice

fib(4)
/ \
fib(3) fib(2)
/ \ / \
fib(2) fib(1) fib(1) fib(0)
/ \
fib(1) fib(0)
/
fib(0)

Instead of recomputing values throughout the tree of recursive calls we can instead use memoization to compute the values once and store them in a hash table. That way, when we need to compute the value again, we instead return the stored value from table and greatly improve the time complexity of the recursive algorithm.

// improving time complexity from O(2^n) to O(n) time
// O(n) time and O(n) space
int getNthFib(int n) {
// memoization with the simple recursive solution
unordered_map<int, int> memo;
memo[0] = 0;
memo[1] = 1;
return fibHelper(n, memo);
}

int fibHelper(int n, unordered_map<int, int> &memo) {
if (n == 0) return 0;
if (n == 1) return 1;
if (memo.find(n) == memo.end()) {
// value doesn't exist in table yet,
// so we compute it and store it in the table
memo[n] = fibHelper(n-1, memo) + fibHelper(n-2, memo);
}
// otherwise we have stored the value already in table
// so simple return the stored value instead of recomputing
return memo[n];
}
			  fib(4)
/ \
fib(3) m[2]
/ \ / \
fib(2) m[1] m[1] m[0]
/ \
fib(1) m[0]
/
fib(0)

If you're having trouble understanding the recursive algorithms, go ahead and watch Algorithms: Memoization and Dynamic Programming by the HackerRank channel on Youtube. Gayle Laakmann McDowell (author of Cracking the Coding Interview) does an incredible job of explaining recursion, dynamic programming and memoization.

Table of contents

Share