Factorial Conversion

Problem Statement

Write a Java program that implements a tail-recursive method to compute the factorial of a non-negative integer (n) using an accumulator to track the running product, and convert this tail-recursive implementation to an iterative version. The program should return the factorial of (n) and test both methods with various inputs, including large values, while measuring stack usage by catching StackOverflowError for recursive calls. You can visualize this as calculating the number of ways to arrange (n) books on a shelf, either by recursively multiplying and passing the product forward or by iteratively accumulating the product.

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 \leq n \leq 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 tailRecursiveFactorial(n, accumulator)
    IF n < 0 THEN
        RETURN -1
    ENDIF
    IF n equals 0 THEN
        RETURN accumulator
    ENDIF
    SET newAccumulator to accumulator * n
    RETURN tailRecursiveFactorial(n - 1, newAccumulator)
ENDFUNCTION

FUNCTION iterativeFactorial(n)
    IF n < 0 THEN
        RETURN -1
    ENDIF
    IF n equals 0 THEN
        RETURN 1
    ENDIF
    SET result to 1
    FOR i from 1 to n
        SET result to result * i
    ENDFOR
    RETURN result
ENDFUNCTION

FUNCTION mainFactorial(n)
    TRY
        CALL tailRecursiveFactorial(n, 1)
    CATCH StackOverflowError
        PRINT "Stack overflow occurred"
    ENDTRY
    CALL iterativeFactorial(n)
    RETURN results
ENDFUNCTION

Algorithm Steps

1. For the tail-recursive approach: a. Check if (n) is negative. If so, return -1, as factorial is undefined for negative numbers. b. Define a tail-recursive helper function that takes (n) and an accumulator as parameters. c. Implement the base case: if (n = 0), return the accumulator. d. For the recursive case, multiply the accumulator by (n) and recursively call the function with (n - 1) and the updated accumulator. e. Call the helper function with the initial accumulator set to 1.
2. For the iterative approach: a. Check if (n) is negative. If so, return -1. b. Check if (n = 0). If so, return 1. c. Initialize a variable result to 1. d. Iterate from 1 to (n), multiplying result by each integer. e. Return the final result.
3. Test both methods with various inputs, including large values (e.g., (n = 20)), and wrap the tail-recursive call in a try-catch block to detect StackOverflowError.
4. Measure stack usage by observing whether StackOverflowError occurs for large inputs in the recursive method.

Java Implementation

public class FactorialConversion {
    // Computes factorial using tail recursion
    public long tailRecursiveFactorial(int n) {
        // Check for invalid input
        if (n < 0) {
            return -1;
        }
        // Call tail-recursive helper with initial accumulator
        try {
            return tailRecursiveFactorialHelper(n, 1);
        } catch (StackOverflowError e) {
            System.out.println("Stack overflow occurred for n = " + n);
            return -1;
        }
    }

    // Helper function for tail-recursive factorial
    private long tailRecursiveFactorialHelper(int n, long accumulator) {
        // Base case: n = 0 returns accumulator
        if (n == 0) {
            return accumulator;
        }
        // Recursive case: multiply accumulator by n and recurse
        return tailRecursiveFactorialHelper(n - 1, accumulator * n);
    }

    // Computes factorial using iteration
    public long iterativeFactorial(int n) {
        // Check for invalid input
        if (n < 0) {
            return -1;
        }
        // Base case: 0! = 1
        if (n == 0) {
            return 1;
        }
        // Initialize result
        long result = 1;
        // Multiply numbers from 1 to n
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        // Return final result
        return result;
    }
}

Output

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

120

Explanation: The factorial of 5 is (5 * 4 * 3 * 2 * 1 = 120).

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

1

Explanation: The factorial of 0 is defined as 1.

For a large input (n = 20), both methods output:

2432902008176640000

Explanation: The factorial of 20 is computed correctly within the long range.

For a very large input (e.g., (n = 10000)), the tail-recursive method may output:

Stack overflow occurred for n = 10000
-1

Explanation: Java’s lack of tail-call optimization causes a stack overflow, while the iterative method may overflow the long data type but avoids stack issues.

How It Works

• Tail-Recursive Approach:
  • Step 1: The tailRecursiveFactorial method checks if (n < 0). For (n = 5), it calls the helper with accumulator = 1.
  • Step 2: In tailRecursiveFactorialHelper:
    • For (n = 5): accumulator = 1 * 5 = 5, recurse with (n = 4, accumulator = 5).
    • For (n = 4): accumulator = 5 * 4 = 20, recurse with (n = 3, accumulator = 20).
    • For (n = 3): accumulator = 20 * 3 = 60, recurse with (n = 2, accumulator = 60).
    • For (n = 2): accumulator = 60 * 2 = 120, recurse with (n = 1, accumulator = 120).
    • For (n = 1): accumulator = 120 * 1 = 120, recurse with (n = 0, accumulator = 120).
    • For (n = 0): Base case, return accumulator = 120.
  • Example Trace: For (n = 5), the accumulator builds: (1 \rightarrow 5 \rightarrow 20 \rightarrow 60 \rightarrow 120), returning 120.
  • Stack Usage: The function is tail-recursive, but Java does not optimize tail recursion, so each call adds a stack frame, leading to O(n) stack usage and potential StackOverflowError for large (n).
• Iterative Approach:
  • Step 1: The iterativeFactorial method checks if (n < 0) or (n = 0). For (n = 5), it initializes result = 1.
  • Step 2: Iterates from 1 to 5:
    • (i = 1): result = 1 * 1 = 1.
    • (i = 2): result = 1 * 2 = 2.
    • (i = 3): result = 2 * 3 = 6.
    • (i = 4): result = 6 * 4 = 24.
    • (i = 5): result = 24 * 5 = 120.
  • Example Trace: For (n = 5), multiplies (1 * 2 * 3 * 4 * 5 = 120).
  • Stack Usage: The iterative approach uses O(1) stack space, as it avoids recursive calls, making it immune to StackOverflowError.
• Comparison: Both methods are O(n) time, but iterative is more space-efficient (O(1) vs. O(n)). For large inputs, the tail-recursive method may throw StackOverflowError, while the iterative method is limited only by long overflow.

Complexity Analysis Table

Note:

• n is the input integer.
• Time complexity: O(n) for both, as tail-recursive makes n calls, and iterative performs n multiplications.
• Space complexity: O(n) for tail-recursive due to the call stack (Java does not optimize tail recursion); O(1) for iterative, using only a single variable.
• Best, average, and worst cases are O(n) for both.

✅ Tip: Convert tail-recursive functions to iterative versions to eliminate stack overflow risks in Java. Test with large inputs (e.g., (n = 1000)) to observe stack overflow in the recursive version and verify correctness in the iterative version.

⚠ Warning: Java does not optimize tail recursion, so the O(n) space complexity may cause StackOverflowError for large inputs. Be cautious with inputs larger than 20, as factorial results may exceed the long data type’s capacity, causing overflow.