[7.3-7.7] fibonacci sequence

1. Implementation
O(n^n)no cache VS O(n) memoization

Quite an improvement: from 19 seconds to 0.000311 seconds.

When the result of a method call is cached to save recalculating the result again later, this is called

memoization.

 Using return with if Statemen ts

Whenever you have a return statement inside an if statement, you do not need

to provide an else clause. If an if statement condition is false, the code execution

continues after the block. If the statement is true, the method execution will finish

with the return statement.

This has the advantage that your code does not need an extra level of indentation

due to the redundant else block:

if (condition) {

// code for condition == true

return valueIfTrue;

}

// more code for condition == false

return valueIfFalse;

// Write a method that returns a Fibonacci sequence from 1 to n.
// n the number of sequence integer

// Iterative - a,b,c

public static List fibonacci (int n)
{
     if (n < 0)
         throw new IllegalArgumentException("n must not be less htan zero");
     if ( n ==0 )
          return new ArrayList<>();
     if ( n ==1)
          return Arrays.asList(0);// 1 number 
     if ( n ==2)
          return Arrays.asList(0,1);// 2 numbers



     final List seq = new ArrayList(n);// n numbers
     seq.add(0);
     n = n-1;
     seq.add(1);
     n = n-1;
 
      
     while ( n > 0 )
     {
          int a = seq.get( seq.size()-1 );
          int b = seq.get( seq.size()-2 );
          seq.add(a+b);
          n = n-1;
     }


     return seq;
     
}

@Test
public void finbonacciseqTest()
{
     fibonacci(-1);
     assertEquals(0, fibonacci(0).size());
     assertEquals(Arrays.asList(0) , fibonacci(1);
     assertEquals(Arrays.asList(0,1), fibonacci(2);
     assertEquals(Arrays.asList(0,1,1), fibonacci(3);
     assertEquals(Arrays.asList(0,1,1,2), fibonacci(4);
     assertEquals(Arrays.asList(0,1,1,2,3), fibonacci(5);
     assertEquals(Arrays.asList(0,1,1,2,3,5), fibonacci(6);
     assertEquals(Arrays.asList(0,1,1,2,3,5,8), fibonacci(7);
     assertEquals(Arrays.asList(0,1,1,2,3,5,8,13), fibonacci(8);
}

// Write a method that returns the nth value of the Fibonacci sequence

// 1. previous method return seq.get(seq.size()-1)



public static int fibN(int n)
{
    if (  n < 0 )
          throw new IllegalArgumentException("n must be not less than zero");
    if ( n ==1 ) return 1;
    if ( n ==0 ) return 0;


    return fibN(n-1) + fibN(n-2);


}

// Caching previously computed Fibonacci numbers
public class Solution {


private Map fibCache = new Map<>();


public int cacheFibN(int n)
{
      if (n < 0 )
           throw IllegalArgumentException("n must be less than zero");
     fibcache.put(0,0);
     fibcache.put(1,1);
     return recursiveCachedFibN(n);
}


private int recursiveCachedFibN(int n)
{
     if (fibCache.constiansKey(n))
        return fibCache.get(n);

     

     int value = recursiveCachedFibN(n-1)+ recursiveCachedFibN(n-2);
     fiCache.put(n, value);
     


     return value;
    

}


}


@Test
public void largeFib()
{
     final long nonCachedStart = System.nanoTime();
     assertEquals(1134903170, fib(45));
     final long nonCachedFinish = System.nanoTime();

     assertEquals(1134903170, cachedFibN(45));
     final long cachedFinish = System.nanoTime();


     System.out.printf("", nonChacedFinish- nonCachedStart );

}