Factorial with Memoization

Problem Statement

Write a Java program that implements a recursive factorial function using memoization with a HashMap to cache previously computed results. The program should compute the factorial of a non-negative integer and compare its performance with a standard recursive factorial implementation for large inputs. Test the program with various inputs, including edge cases like 0 and 1. You can visualize this as calculating the number of ways to arrange books on a shelf, where memoization saves time by reusing previously calculated arrangements.

Input: A non-negative integer n (e.g., n = 5). Output: A long integer representing the factorial of n (e.g., 120 for n = 5). Constraints:

• 0 ≤ n ≤ 20 (to avoid overflow with long).
• The input is a non-negative integer. Example:
• Input: n = 5
• Output: 120
• Explanation: The factorial of 5 is 5 * 4 * 3 * 2 * 1 = 120.
• Input: n = 0
• Output: 1
• Explanation: The factorial of 0 is defined as 1.

Pseudocode

FUNCTION factorialWithMemo(n, memo)
    IF n < 0 THEN
        RETURN -1
    ENDIF
    IF n equals 0 OR n equals 1 THEN
        RETURN 1
    ENDIF
    IF n exists in memo THEN
        RETURN memo[n]
    ENDIF
    SET result to n * factorialWithMemo(n - 1, memo)
    SET memo[n] to result
    RETURN result
ENDFUNCTION

FUNCTION mainFactorial(n)
    CREATE empty HashMap memo
    RETURN factorialWithMemo(n, memo)
ENDFUNCTION

Algorithm Steps

1. Check if the input n is negative. If so, return -1, as factorial is undefined for negative numbers.
2. Define a recursive helper function that takes the input n and a HashMap for memoization as parameters.
3. In the recursive function, implement the base cases: if n is 0 or 1, return 1, as the factorial of 0 and 1 is 1.
4. Check if the factorial of n is already in the HashMap. If so, return the cached result.
5. For the recursive case, compute the factorial by multiplying n with the result of the recursive call for n - 1.
6. Store the computed result in the HashMap with n as the key.
7. In the main function, create an empty HashMap and call the helper function with n and the HashMap.
8. Return the final factorial result.

Java Implementation

import java.util.HashMap;

public class FactorialWithMemoization {
    // Computes factorial of n using memoization with HashMap
    public long factorial(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 factorialHelper(n, memo);
    }

    // Helper function for recursive factorial with memoization
    private long factorialHelper(int n, HashMap<Integer, Long> memo) {
        // Base case: factorial of 0 or 1 is 1
        if (n == 0 || n == 1) {
            return 1;
        }
        // Check if result is in memo
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        // Recursive case: n * factorial(n-1)
        long result = n * factorialHelper(n - 1, memo);
        // Cache result in memo
        memo.put(n, result);
        return result;
    }

    // Standard recursive factorial for comparison
    public long standardFactorial(int n) {
        // Check for invalid input
        if (n < 0) {
            return -1;
        }
        // Base case: factorial of 0 or 1 is 1
        if (n == 0 || n == 1) {
            return 1;
        }
        // Recursive case: n * factorial(n-1)
        return n * standardFactorial(n - 1);
    }
}

Output

For the input n = 5, the factorial method outputs:

120

Explanation: The factorial of 5 is computed as 5 * 4 * 3 * 2 * 1 = 120.

For the input n = 0, the factorial method outputs:

1

Explanation: The factorial of 0 is defined as 1.

For the input n = 15, the factorial method outputs:

1307674368000

Explanation: The factorial of 15 is computed as 15 * 14 * ... * 1 = 1307674368000.

How It Works

• Step 1: The factorial method checks if n is negative. For n = 5, it is valid, so it creates a HashMap and calls factorialHelper.
• Step 2: In factorialHelper:
  • For n = 5: Not in memo, compute 5 * factorialHelper(4).
  • For n = 4: Not in memo, compute 4 * factorialHelper(3).
  • For n = 3: Not in memo, compute 3 * factorialHelper(2).
  • For n = 2: Not in memo, compute 2 * factorialHelper(1).
  • For n = 1: Base case, return 1.
  • Unwind: Store 2! = 2 in memo, 3! = 6 in memo, 4! = 24 in memo, 5! = 120 in memo, return 120.
• Step 3: For subsequent calls with cached values (e.g., in a performance test), the memoized function retrieves results directly from the HashMap, reducing computation.
• Example Trace: For n = 5, the algorithm computes: 5 * (4 * (3 * (2 * (1)))) = 5 * 24 = 120, caching each intermediate result. For n = 0, it returns 1 immediately.
• Performance Comparison: The memoized version is faster for repeated calls or large n within the same HashMap, as it avoids recomputing factorials. For example, computing 15! takes O(n) time without memoization but O(1) for cached values with memoization.

Complexity Analysis Table

Note:

• n is the input integer.
• Time complexity (memoized): O(n) for the first call to compute and cache results up to n; O(1) for subsequent calls if cached.
• Time complexity (standard): O(n) for all calls, as it recomputes each step.
• Space complexity: O(n) for both, due to the recursive call stack and HashMap (for memoized version).
• Best case (memoized): O(1) if the result is cached; worst case is O(n) for initial computation.

✅ Tip: Use memoization to optimize recursive functions like factorial for repeated calls or large inputs, and test with edge cases like 0, 1, and large values (within constraints) to verify correctness.

⚠ Warning: Be cautious with inputs larger than 20, as factorial results may exceed the long data type’s capacity, causing overflow. Ensure the HashMap is properly initialized to avoid NullPointerException.