Fibonacci

Recursion

public static int fibonacci(int n) {
   if (n == 0) {
       return 0;
   }
   if (n == 1) {
       return 1;
   }
   return fibonacci(n - 1) + fibonacci(n - 2);
}

• Time Complexity: O (2^n)
• Space Complexity: O(1)

Recursion without repetition

public static int fibonacci1(int n) {
   int [] arr = new int[n+1];
   return recurse(arr,n);

private static int recurse (int[] arr, int n){
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (arr[n]!=0){
        return arr[n];
    }
    arr[n] = recurse(arr, n - 1) + recurse(arr, n - 2);
    return arr[n];
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Two pointer iteration

private static int iterate (int[] arr, int n){
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int low = 0,high = 1;
    for (int i = 2; i <= n; i++) {
        int sum = low + high;
        low = high;
        high = sum;
    }
    return high;
}

• Time Complexity: O(n)
• Space Complexity: O(1)