DEV Community: Khalil Saboor

Fibonacci: Recursion vs Iteration

Khalil Saboor — Thu, 08 Nov 2018 00:55:10 +0000

A common whiteboard problem that I have been asked to solve couple times, has been to "write a function to generate the nth Fibonacci number starting from 0,1". In this post, however, I want to address a common follow up question for this problem and that is what method is more efficient for solving this problem Recursion or Iteration.

NOTE

It best practice to always attempt this problem before reading further into the article. So I listed out a few common tools for completing this problem.

Pen/Marker
Notebook/WhiteBoard
VS Code
The Internet

The Fibonacci numbers are a sequence of integers in
which the first two elements are 0 & 1, and each following
elements are the sum of the two preceding elements:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ..., 233

The Problem

Write a function to generate the nth Fibonacci number.
The nth Fibonacci number is given by:

Fn = Fn-1 + Fn-2
The first two terms of the series are 0, 1.
For example: fib(0) = 0, fib(1) = 1, fib(2) = 1

Solution #1 Using Recursion


public static int fibonacciRecursion(int nthNumber) {
        //use recursion
        if (nthNumber == 0) {

            return 0;

        } else if (nthNumber == 1) {

            return 1;
        }   
     return fibonacciRecursion(nthNumber - 1) + fibonacciRecursion(nthNumber - 2);
    }

Analysis

By using Recursion to solve this problem we get a cleanly written function, that checks. If the given number is equal to 0 and 1 we return both given numbers.

If we pass a number that is greater than 0 and 1. Then we make two recursive calls where we add both calls with the nthNumber minus 1 and 2 in both calls.

Passing these Integers 0, 1, 2, 3, 4, 5, Will most likely give us --> 0, 1, 1, 2, 3, 5 in a timely fashion.

But what happens if we pass higher numbers like 50, 67, 100. Well if you try to run the function with the given numbers in you're IDE. You will begin to notice how much longer it takes for this method gives us our Fibonacci number. Now trying to run a Space Complexity analysis will be a tricky thing to do because of a lot of things are happening behind the scenes of this recursive function. The reason for the poor performance is heavy push-pop of the stack memory in each recursive call.

Now for a way around this would be using memorization and storing each Fibonacci calculated so. But for now, I'm going to move along to the Iteration method and why it would compute our 100th Fibonacci number faster.

Solution #2 Using Iteration


 public static int fibonacciLoop(int nthNumber) {
        //use loop
        int previouspreviousNumber, previousNumber = 0, currentNumber = 1;

        for (int i = 1; i < nthNumber ; i++) {

            previouspreviousNumber = previousNumber;

            previousNumber = currentNumber;

            currentNumber = previouspreviousNumber + previousNumber;

        }
        return currentNumber;
    }

Analysis

The Iteration method would be the prefer and faster approach to solving our problem because we are storing the first two of our Fibonacci numbers in two variables (previouspreviousNumber, previousNumber) and using "CurrentNumber" to store our Fibonacci number. Storing these values prevent us from constantly using memory space in the Stack. Thus giving us a time complexity of O(n).

For more information on Stack and Heap memory in the context of Java

For more information on Dynamic programming approach

How should I go about creating a portfolio site?

Khalil Saboor — Sat, 20 Oct 2018 00:48:14 +0000

Hey Guys, I wanted to know if I could get some pointers on going about creating my first Portfolio site. I'm open to videos, posts, and example portfolio sites.

A little about me: I'm mostly a Back-End Developer (Java) (little Python/Go) with a repo of Console applications, Two SpringBoot App and a few Front-End projects. I have a Basic background of Front-End tools like HTML, CSS, and JS from the old Free Code Camp site.

One of the main things I wanted to know is if I should use a framework like React or Vue.JS or write it basic HTML, CSS, and JS as a single page? Also, I found a tutorial where a guy walks through creating a modern Portfolio site (Traversy Media no Framework ). But I feel like it would be checking to just follow along and create it.

Great questions for YOU to ask during a Technical Interview

Khalil Saboor — Tue, 16 Oct 2018 20:41:23 +0000

Introduction

As someone who has bomb their first 6 technical interviews. I as feel as though I should write about my experiences and inform the masses about what they should know before heading into a technical interview.

While I did sort them into HR and Dev. I have had in my experience ask both Hiring managers and Developers question on either pool these questions. Also, It's best to not assume your Hiring manager is not technical. You'll be surprised what are their response is to the questions I have listed for Developers.

For Hiring Managers

Do you have a business card?
What are the career growth opportunities for someone in this position?
How does [company name] help developers stay in sync with current technologies?
What is the most impactful thing I could do starting out at [company name]?
What does the onboarding process look like for new candidates?

For Developer/Lead/managers

What do you enjoy most about working at [company name]?
Could you tell me your team technical stack?
What does the average day look like for you?
What will my role be during the first couple of months at [company name]?
What performance metrics do you use to determine a successful ticket/feature is completes?
Can you tell me a recent project or feature you that you feel proud?

Quick intro about myself:

I have been learning how to become a Software Developer for roughly 4 years now. A large part of my learning has been self-taught w/Free Code Camp and Youtube. I just recently graduated from a 12 week Java base Coding BootCamp called Zip Code Wilmington. But I have had knowledge of Java and Computer Programming since High School. I'm currently mentoring someone in JavaScript and Front-End Development using the same Free Code Camp and Codecademy. I've planned on writing some more post my prior experiences on technical interviews.

Hi, I'm Khalil Saboor

Khalil Saboor — Sun, 28 May 2017 00:00:43 +0000

I have been coding for 3 years.

You can find me on Twitter as @justcallme_lil

I live in Philadelphia.

I work for No Company as of now

I mostly program in these languages: HTML, CSS, Js.

I am currently learning more about Front-End and Swift.

Nice to meet you.