fork download 
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.List;
  4. import java.util.Map;
  5. import java.util.function.Function;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone {
  9.     private static Map<Integer, Integer> fibonacciNumbers = new HashMap<>();
  10.  
  11.     public static void main(String[] args) throws java.lang.Exception {
  12.         int[] testCases = {0, 1, 2, 3, 4, 5, 10, 40};
  13.  
  14.         System.out.println("iterational algorighm");
  15.         runTestCase(Ideone::getFibonacciNumber, testCases);
  16.  
  17.         System.out.println("recursive algorighm");
  18.         runTestCase(Ideone::getFibonacciNumberRec, testCases);
  19.  
  20.         System.out.println("recursive algorighm with memoization");
  21.         runTestCase(Ideone::getFibonacciNumberRec2, testCases);
  22.     }
  23.  
  24.     public static int getFibonacciNumber(int n) {
  25.         int previous1 = 1, previous2 = 1;
  26.         int current = 1;
  27.         for (int i = 1; i < n; i++) {
  28.             current = previous1 + previous2;
  29.             previous2 = previous1;
  30.             previous1 = current;
  31.         }
  32.  
  33.         return current;
  34.     }
  35.  
  36.     public static int getFibonacciNumberRec(int n) {
  37.         if (n < 2) return 1;
  38.         return getFibonacciNumberRec(n - 1) + getFibonacciNumberRec(n - 2);
  39.     }
  40.  
  41.     public static int getFibonacciNumberRec2(int n) {
  42.         return fibonacciNumbers.computeIfAbsent(n,  i -> 
  43.                 (i < 2) ? 1 : getFibonacciNumberRec2(i - 1) + getFibonacciNumberRec2(i - 2));
  44.     }
  45.  
  46.     private static void runTestCase(Function<Integer, Integer> function, int[] testCases) {
  47.         long time = System.currentTimeMillis();
  48.         for (int testCase : testCases) {
  49.             System.out.println(function.apply(testCase));
  50.         }
  51.         System.out.println("Execution time - " + (System.currentTimeMillis() - time) + "ms");
  52.     }
  53. }
Success #stdin #stdout 0.57s 33660KB
comments (?)
stdin 
Standard input is empty
stdout 
iterational algorighm
1
1
2
3
5
8
89
165580141
Execution time - 1ms
recursive algorighm
1
1
2
3
5
8
89
165580141
Execution time - 427ms
recursive algorighm with memoization
1
1
2
3
5
8
89
165580141
Execution time - 1ms
https://ideone.com/Ovt4l7
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!