JavaScript Fibonacci

Here is a Fibonacci series code in JavaScript that uses Memoization technique of Dynamic Programming.

(function(){
  //suppose we want to find the first 10 terms
  'use strict';
  var fibArray = [];
  
  findFibByRec(10);
  
  function findFibByRec(number){
     for(var i = 0; i <= number; i++){
         console.log(fibRec(i));
     }
  }
  
  function fibRec(num){
     if(num == 0){
       fibArray[0] = 0;
       return 0;
     }
     
     if(num == 1 || num == 2){
       fibArray[num] = 1;
     }
     
     if(fibArray[num]){
        return fibArray[num];
     }
     
     if(!fibArray[num]){
       
       fibArray[num] = fibRec(num -1) + fibRec(num -2);
       return fibArray[num];
     }
  
  }

})()

REST WebServices

REST = Representational State Transfer

REST is a set of rules, that when followed, enable you to build a distributed application that has a specific set of desirable constraints.

Features:

1. It is stateless which means that ideally no connection should be maintained between the client and server. 
2. It is the responsibility of the client to pass its context to the server and then the server can store this context to process the client's further request. For example, session maintained by server is identified by session identifier passed by the client.

Advantages of Statelessness:

1. Web Services can treat each method calls separately.
2. Web Services need not maintain the client's previous interaction.
3. This in turn simplifies application design.
4. HTTP is itself a stateless protocol unlike TCP and thus RESTful Web Services work seamlessly with the HTTP protocols.

Disadvantages of Statelessness:

1. One extra layer in the form of heading needs to be added to every request to preserve the client's state.
2. For security we may need to add a header info to every request.

HTTP Methods supported by REST:

GET: /string/someotherstring 

It is idempotent and should ideally return the same results every time a call is made

PUT: 

Same like GET. Idempotent and is used to update resources.

POST: should contain a url and body

Used for creating resources. Multiple calls should ideally return different results and should create multiple products.

DELETE:

Used to delete resources on the server. 

HEAD:

The HEAD method is identical to GET except that the server MUST NOT return a message-body in the response. The meta information contained in the HTTP headers in response to a HEAD request SHOULD be identical to the information sent in response to a GET request.

OPTIONS:

This method allows the client to determine the options and/or requirements associated with a resource, or the capabilities of a server, without implying a resource action or initiating a resource retrieval.

HTTP Responses

Go here for all the responses.

Here are a few important ones:

200 - OK

3XX - Additional information needed from the client and url redirection

400 -  Bad request

401 - Unauthorized to access

403 - Forbidden

The request was valid, but the server is refusing action. The user might not have the necessary permissions for a resource, or may need an account of some sort.

404 - Not FoundThe requested resource could not be found but may be available in the future. Subsequent requests by the client are permissible.

^[36]405 - Method Not Allowed
A request method is not supported for the requested resource; for example, a GET request on a form that requires data to be presented via POST, or a PUT request on a read-only resource.

404 - Request not found

500 - Internal Server Failure

502 - Bad Gateway Error

Fibonacii Comparison

Here is an analysis on the three techniques which you can use for Fibonacci:

1. For Loop
2. Recursion
3. Memoization

Here is my code to test all three:

public class Fibonnaci {
    // Output = 0 1 1 2 3 5 8 13

    static int fibMemo[];

    public static void main(String args[]) {
        int num = 20;

        System.out.println("By For Loop");
        Long startTimeForLoop = System.nanoTime();
        // returns the fib series
        int fibSeries[] = fib(num);
        for (int i = 0; i < fibSeries.length; i++) {
            System.out.print(" " + fibSeries[i] + " ");
        }
        Long stopTimeForLoop = System.nanoTime();
        System.out.println("");
        System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));


        System.out.println("By Using Recursion");
        Long startTimeRecursion = System.nanoTime();
        // uses recursion
        int fibSeriesRec[] = fibByRec(num);

        for (int i = 0; i < fibSeriesRec.length; i++) {
            System.out.print(" " + fibSeriesRec[i] + " ");
        }
        Long stopTimeRecursion = System.nanoTime();
        System.out.println("");
        System.out.println("For Loop Time:" + (stopTimeRecursion -startTimeRecursion));



        System.out.println("By Using Memoization Technique");
        Long startTimeMemo = System.nanoTime();
        // uses memoization
        fibMemo = new int[num];
        fibByRecMemo(num-1);
        for (int i = 0; i < fibMemo.length; i++) {
            System.out.print(" " + fibMemo[i] + " ");
        }
        Long stopTimeMemo = System.nanoTime();
        System.out.println("");
        System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));

    }


    //fib by memoization

    public static int fibByRecMemo(int num){

        if(num == 0){
            fibMemo[0] = 0;
            return 0;
        }

        if(num ==1 || num ==2){
          fibMemo[num] = 1;
          return 1; 
        }

        if(fibMemo[num] == 0){
            fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
            return fibMemo[num];
        }else{
            return fibMemo[num];
        }

    }


    public static int[] fibByRec(int num) {
        int fib[] = new int[num];

        for (int i = 0; i < num; i++) {
            fib[i] = fibRec(i);
        }

        return fib;
    }

    public static int fibRec(int num) {
        if (num == 0) {
            return 0;
        } else if (num == 1 || num == 2) {
            return 1;
        } else {
            return fibRec(num - 1) + fibRec(num - 2);
        }
    }

    public static int[] fib(int num) {
        int fibSum[] = new int[num];
        for (int i = 0; i < num; i++) {
            if (i == 0) {
                fibSum[i] = i;
                continue;
            }

            if (i == 1 || i == 2) {
                fibSum[i] = 1;
                continue;
            }

            fibSum[i] = fibSum[i - 1] + fibSum[i - 2];

        }
        return fibSum;
    }

}

Here are the results:

By For Loop
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
For Loop Time:347688
By Using Recursion
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
For Loop Time:767004
By Using Memoization Technique
 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377  610  987  1597  2584  4181 
Memoization Time:327031

Hence we can see for loop is the best time wise and memoization matches closely.

But recursion takes the longest and may be you should avoid in real life. Also if you are using recursion make sure that you optimize the solution.