Print Fibonacci Series in Reverse Order

Reading time: 30 minutes | Coding time: 10 minutes

In Fibonacci series each number is the sum of 2 preceding ones starting from 0 and 1.

F(0) = 0, F(1) = 1,and F(n) = F(n-1)+F(n-2) for n>1

In this article, we will explore how to print fibonacci series in reverse order.

A key point to note here is that as Fibonacci number depends on previous fibonacci numbers, we have to generate it in forward pass that is in order. Instead of printing it directly, we can delay it to print it in reverse order.

Naive Approach

In this approach, we keep on storing Fibonacci numbers by computing them using the recurrence relation and once we have reached our goal we print the Fibonacci array in reverse.

The function fib(n) simply returns the sum of fib(n-1) and fib(n-2) which then recurse and keep summing values until they reach base cases.

Code:

#include <iostream>
#include <vector>
using namespace std;
int fib(int n){
    if(n == 0)return 0;
    else if(n == 1)return 1;
    return fib(n-1) + fib(n - 2);
}
int main () {
    
    int n = 10;
    std::vector<int> V; // vector to store the Fibonacci numbers.

    V.push_back(0); // fib(0) = 0
    V.push_back(1); // fib(1) = 1

    for(int i=2; i<=n; i++) {
        V.push_back(fib(i)); // fib(i) = fib(i-1)+fib(i-2); 
    }
    // reversing the vector to get required series
    int l = 0, r = V.size()-1;
    while(l<r){
        swap(V[l],V[r]);
        l++;
        r--;
    }
    // printing the Fibonacci series in reverse order
    for(int element: V){
        std::cout<<element<<" ";
    }

    return 0;
}

fib(int n) is the function that computes fibinacci number. It handles 2 edge cases when n == 1 and n == 0, all the other values of n are computed using the reccurence relation.

Time Complexity:

T(n) = T(n-1) + T(n-2) + O(1)

The above time complexity relation is derived from the recurence relation where to calculate fib(n) we first compute fib(n-1) and fib(n-2) and perform an addition of O(1) time.

The overall complexity thus becomes O(2^n) which is termed as exponential.

Dynamic Programming

Dynamic Programming is an algorithmic technique in which the key idea is to store the values of smaller problems such that in case, the value is required again, it will return the value instead of recomputing. This works in problems which can be broken into smaller problems and smaller problems are encountered multiple times. When applicable, dynamic programming can reduce time complexity greatly.

One key observation we can make in the naive approach described above is that to compute fib(n) we call fib(n-1) and fib(n-2), later to compute fib(n-1) we call fib(n-2) and fib(n-3), as we can see fib(n-2) is being called twice even though its return value remains the same for both the function calls, which as explained is the perfect scenario for us to use dynamic programming.

Recursive DP

Assume fib[i] represents ith Fibonacci number and to compute this we need two previous values namely fib[i-1] and fib[i-2], if we create a check for each function call to check if some other function call has already answered this query then we can just return this number from the memo table in O(1) time without having to recalculate it.

fib[i] = fib[i-1] + fib[i-2]

Below is the code for the above-discussed approach.

Pseudocode:

function Fibonacci(index i, array &memo):
	if(i == 0) return 0
    if(i == 1) return 1
    if(memo[i] != null) return memo[i];
    memo[i] = Fibonacci(i-1, memo) + Fibonacci(i - 2, memo)
    return memo[i]

Code:

#include <iostream>
#include <vector>
using namespace std;
int fib(int n, vector<int> &dp){
    if(n == 0)return 0;
    else if(n == 1)return 1;
    if(dp[n])return dp[n];
    dp[n] =  fib(n-1) + fib(n - 2);
    return dp[n];
}
int main () {
    
    int n = 10;
    std::vector<int> V; // vector to store the Fibonacci numbers.
    std::vector<int> dp(n+1,0); //Memo table
    V.push_back(0); // fib(0) = 0
    V.push_back(1); // fib(1) = 1
    
    for(int i=2; i<=n; i++) {
        V.push_back(fib(i,dp)); // fib(i) = fib(i-1)+fib(i-2); 
    }
    // reversing the vector to get required series
    int l = 0, r = V.size()-1;
    while(l<r){
        swap(V[l],V[r]);
        l++;
        r--;
    }
    // printing the Fibonacci series in reverse order
    for(int element: V){
        std::cout<<element<<" ";
    }

    return 0;
}

Time Complexity:

T(n) = O(n)

We never compute any Fibonacci number more than once and to compute any number we perform either vector lookups of precomputed Fibonacci numbers or compute them once, hence our overall time complexity becomes O(n).

Dry run:

This is how our function call tree will look like when we call fib(6).
those red crosses represent the function calls that didn't calculate the Fibonacci value and returned precomputed values from memo table instead.

Iterative DP

Even though the recursive DP seems like a great leap in time complexity optimization but there is still a problem with it.
Function call overhead is constant time factor compilers take to process which function to call before actually executing the function itself, hence if possible iterative code is preferred over recursive ones whenever possible as they generally perform better.

In this approach we initialize fib[0] and fib[1] then starting from 3rd element of vector fib we go on calculating fib[i] = fib[i-1]+fib[i-2] incrementing i till we reach i == n then we stop and return the vector fib in reverse.

Pseudocode:

function Fibonacci(index i):
	/*Create array of required length*/
	integer array fib[i+1]
	fib[0]=0
	fib[1]=1
	/*Loop over the array and calculate the numbers at all positions*/
	for(i=2 to i+1)
		fib[i]=fib[i-1]+fib[i-2]
	return fib[i+1]

Code:

#include <iostream>
#include <vector>
using namespace std;

int main () {
    
    int n = 10;
    std::vector<int> V; // vector to store the Fibonacci numbers.

    V.push_back(0); // fib(0) = 0
    V.push_back(1); // fib(1) = 1

    for(int i=2; i<=n; i++) {
        V.push_back(V[i-1] + V[i-2]); // fib(i) = fib(i-1)+fib(i-2); 
    }
    // reversing the vector to get required series
    int l = 0, r = V.size()-1;
    while(l<r){
        swap(V[l],V[r]);
        l++;
        r--;
    }
    // printing the Fibonacci series in reverse order
    for(int element: V){
        std::cout<<element<<" ";
    }

    return 0;
}

Time Complexity:

T(n) = O(n)

Similar to recursive approach We never compute any Fibonacci number more than once also to compute any number we just perform two vector lookups of precomputed Fibonacci numbers hence our overall time complexity becomes O(n).