# 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!
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. }