Advertisement
Guest User

08. Recursive Fibonacci

a guest
May 22nd, 2016
1,903
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.40 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. public class Problem8_RecursiveFibonacci {
  4.  
  5.     private static long[] memo;
  6.  
  7.     public static void main(String[] args) {
  8.         Scanner input = new Scanner(System.in);
  9.  
  10.         int n = Integer.parseInt(input.nextLine());
  11.  
  12.         memo = new long[n + 1];
  13.         System.out.println(recursiveFibonacciWithMemoization(n));
  14.     }
  15.  
  16.     // Recursive fibonacci without DP
  17.     private static long recursiveFibonacci(int n) {
  18.         if (n <= 1) {
  19.             return 1;
  20.         }
  21.  
  22.         return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
  23.     }
  24.  
  25.     // Top down DP: recursion + memoization
  26.     private static long recursiveFibonacciWithMemoization(int n) {
  27.         if (n <= 1) {
  28.             return 1;
  29.         }
  30.  
  31.         if (memo[n] != 0) {
  32.             return memo[n];
  33.         }
  34.  
  35.         memo[n] =
  36.                 recursiveFibonacciWithMemoization(n - 1) +
  37.                         recursiveFibonacciWithMemoization(n - 2);
  38.         return memo[n];
  39.     }
  40.  
  41.     // Bottom up DP
  42.     private static long fibonacciWithBottomUpDP(int n) {
  43.         long[] fibonacciNumbers = new long[n + 1];
  44.  
  45.         fibonacciNumbers[0] = 1;
  46.         fibonacciNumbers[1] = 1;
  47.         for (int i = 2; i <= n; i++) {
  48.             fibonacciNumbers[i] =
  49.                     fibonacciNumbers[i - 1] + fibonacciNumbers[i - 2];
  50.         }
  51.  
  52.         return fibonacciNumbers[n];
  53.     }
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement