Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Fibonacci Optimization

Problem Statement

Write a Java program that computes the nth Fibonacci number using a recursive approach with memoization (using a HashMap to cache results) and an iterative approach. The program should return the nth Fibonacci number and compare the performance of both methods for large inputs. Test the program with various inputs, including edge cases like (n = 0) and (n = 1). You can visualize this as calculating the number of rabbits in a population after (n) months, where each month’s population depends on the previous two, with memoization or iteration to optimize the process.

Input: A non-negative integer (n) (e.g., (n = 6)). Output: A long integer representing the nth Fibonacci number (e.g., 8 for (n = 6)). Constraints:

  • (0 \leq n \leq 50) (to avoid overflow with long).
  • The input is a non-negative integer. Example:
  • Input: (n = 6)
  • Output: 8
  • Explanation: The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, ..., so the 6th Fibonacci number is 8.
  • Input: (n = 0)
  • Output: 0
  • Explanation: The 0th Fibonacci number is defined as 0.

Pseudocode

FUNCTION fibonacciMemo(n, memo)
    IF n < 0 THEN
        RETURN -1
    ENDIF
    IF n equals 0 THEN
        RETURN 0
    ENDIF
    IF n equals 1 THEN
        RETURN 1
    ENDIF
    IF n exists in memo THEN
        RETURN memo[n]
    ENDIF
    SET result to fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo)
    SET memo[n] to result
    RETURN result
ENDFUNCTION

FUNCTION fibonacciIterative(n)
    IF n < 0 THEN
        RETURN -1
    ENDIF
    IF n equals 0 THEN
        RETURN 0
    ENDIF
    IF n equals 1 THEN
        RETURN 1
    ENDIF
    SET prev to 0
    SET current to 1
    FOR i from 2 to n
        SET next to prev + current
        SET prev to current
        SET current to next
    ENDFOR
    RETURN current
ENDFUNCTION

FUNCTION mainFibonacci(n)
    CREATE empty HashMap memo
    CALL fibonacciMemo(n, memo)
    CALL fibonacciIterative(n)
    RETURN results
ENDFUNCTION

Algorithm Steps

  1. For the recursive approach with memoization: a. Check if (n) is negative. If so, return -1, as Fibonacci is undefined for negative numbers. b. Define a recursive helper function that takes (n) and a HashMap for memoization as parameters. c. Implement base cases: if (n = 0), return 0; if (n = 1), return 1. d. Check if the Fibonacci number for (n) is in the HashMap. If so, return the cached result. e. Compute the Fibonacci number as the sum of the results for (n - 1) and (n - 2) using recursive calls. f. Store the result in the HashMap and return it.
  2. For the iterative approach: a. Check if (n) is negative. If so, return -1. b. Implement base cases: if (n = 0), return 0; if (n = 1), return 1. c. Initialize variables prev (F(0) = 0) and current (F(1) = 1). d. Iterate from (i = 2) to (n), computing each Fibonacci number as prev + current, updating prev and current accordingly. e. Return the final Fibonacci number.
  3. In the main function, create a HashMap for memoization, call both methods, and compare their performance for large inputs.

Java Implementation

import java.util.HashMap;

public class FibonacciOptimization {
    // Computes nth Fibonacci number using recursion with memoization
    public long fibonacciMemo(int n) {
        // Check for invalid input
        if (n < 0) {
            return -1;
        }
        // Create HashMap for memoization
        HashMap<Integer, Long> memo = new HashMap<>();
        // Call recursive helper function
        return fibonacciMemoHelper(n, memo);
    }

    // Helper function for recursive Fibonacci with memoization
    private long fibonacciMemoHelper(int n, HashMap<Integer, Long> memo) {
        // Base case: F(0) = 0
        if (n == 0) {
            return 0;
        }
        // Base case: F(1) = 1
        if (n == 1) {
            return 1;
        }
        // Check if result is in memo
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        // Recursive case: F(n) = F(n-1) + F(n-2)
        long result = fibonacciMemoHelper(n - 1, memo) + fibonacciMemoHelper(n - 2, memo);
        // Cache result in memo
        memo.put(n, result);
        return result;
    }

    // Computes nth Fibonacci number using iteration
    public long fibonacciIterative(int n) {
        // Check for invalid input
        if (n < 0) {
            return -1;
        }
        // Base case: F(0) = 0
        if (n == 0) {
            return 0;
        }
        // Base case: F(1) = 1
        if (n == 1) {
            return 1;
        }
        // Initialize variables for F(0) and F(1)
        long prev = 0;
        long current = 1;
        // Iterate to compute F(n)
        for (int i = 2; i <= n; i++) {
            long next = prev + current;
            prev = current;
            current = next;
        }
        // Return nth Fibonacci number
        return current;
    }
}

Output

For the input (n = 6), both methods output:

8

Explanation: The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, so the 6th Fibonacci number is 8.

For the input (n = 0), both methods output:

0

Explanation: The 0th Fibonacci number is defined as 0.

For the input (n = 10), both methods output:

55

Explanation: The 10th Fibonacci number is 55.

How It Works

  • Recursive Approach with Memoization:
    • Step 1: The fibonacciMemo method checks if (n < 0). For (n = 6), it creates a HashMap and calls fibonacciMemoHelper.
    • Step 2: In fibonacciMemoHelper:
      • For (n = 6): Not in memo, compute F(5) + F(4).
      • For (n = 5): Not in memo, compute F(4) + F(3).
      • For (n = 4): Not in memo, compute F(3) + F(2).
      • For (n = 3): Not in memo, compute F(2) + F(1).
      • For (n = 2): Not in memo, compute F(1) + F(0) = 1 + 0 = 1.
      • For (n = 1): Base case, return 1.
      • For (n = 0): Base case, return 0.
      • Unwind: Cache F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8.
    • Example Trace: For (n = 6), computes F(6) = F(5) + F(4) = 5 + 3 = 8, caching each result.
  • Iterative Approach:
    • Step 1: The fibonacciIterative method checks if (n < 0). For (n = 6), initializes prev = 0, current = 1.
    • Step 2: Iterates from (i = 2) to 6:
      • (i = 2): next = 0 + 1 = 1, prev = 1, current = 1.
      • (i = 3): next = 1 + 1 = 2, prev = 1, current = 2.
      • (i = 4): next = 1 + 2 = 3, prev = 2, current = 3.
      • (i = 5): next = 2 + 3 = 5, prev = 3, current = 5.
      • (i = 6): next = 3 + 5 = 8, prev = 5, current = 8.
    • Example Trace: For (n = 6), computes 0, 1, 1, 2, 3, 5, 8, returning 8.
  • Performance Comparison: Memoized recursive is O(n) time, much faster than O(2^n) for naive recursion, and comparable to iterative O(n) time. Iterative uses O(1) space, while memoized uses O(n) space for the HashMap and call stack, making iterative more efficient for very large (n).

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Recursive Call (Memoized)O(n)O(n)
IterationO(n)O(1)
Full Algorithm (Memoized)O(n)O(n)
Full Algorithm (Iterative)O(n)O(1)

Note:

  • n is the input integer.
  • Time complexity: O(n) for memoized recursive, as each Fibonacci number is computed once and cached; O(n) for iterative, as it performs n iterations.
  • Space complexity: O(n) for memoized recursive due to the HashMap and call stack; O(1) for iterative, using only a few variables.
  • Best, average, and worst cases are O(n) for both.

✅ Tip: Use the iterative approach for large (n) to minimize space usage, or memoization for recursive solutions to avoid exponential time complexity. Test with large inputs (e.g., (n = 50)) to compare performance and verify results.

⚠ Warning: Without memoization, recursive Fibonacci has O(2^n) time complexity, making it impractical for large (n). Ensure inputs are within constraints ((n \leq 50)) to avoid overflow with long.