Fibonacci Number Computation: Recursive vs Iterative Approaches

Question

Write two functions to compute the nth Fibonacci number: a) Recursive: public static int fibRecursive(int n); b) Iterative: public static int fibIterative(int n);

Then compare and contrast: - Time complexity - Space complexity - Performance and use cases of these two approaches (recursive vs. non-recursive). - You can safely assume small inputs that can fit primitive integer type (n).

Answer

Implementation

Recursive Implementation

public static int fibRecursive(int n) {
    // Input validation
    if (n < 0) {
        throw new IllegalArgumentException("Input must be non-negative");
    }

    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;

    // Recursive case
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

Iterative Implementation

public static int fibIterative(int n) {
    // Input validation
    if (n < 0) {
        throw new IllegalArgumentException("Input must be non-negative");
    }

    // Base cases
    if (n == 0) return 0;
    if (n == 1) return 1;

    // Iterative computation
    int prev = 0;
    int curr = 1;

    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }

    return curr;
}

Complexity Analysis

Time Complexity

Recursive Approach: O(2^n)

Each recursive call generates two more recursive calls
Creates a binary tree of calls with height n
Total number of nodes ≈ 2^n

Example for n=5:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)
│       ├── fib(1)
│       └── fib(0)
└── fib(3)
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

Iterative Approach: O(n)
- Single loop that runs n-1 times
- Each iteration performs constant time operations
- No redundant calculations
Space Complexity
Recursive Approach: O(n)
- Stack space used by recursive calls
- Maximum depth of recursion is n
- Each call uses constant space
- Total space ≈ n * constant = O(n)
Iterative Approach: O(1)
- Uses only three variables (prev, curr, next)
- Space usage is constant regardless of input size
- No stack space needed

Performance Comparison

Execution Time

public class FibonacciBenchmark {
    public static void main(String[] args) {
        int[] testCases = {10, 20, 30, 40};

        for (int n : testCases) {
            long startTime = System.nanoTime();
            int result = fibRecursive(n);
            long endTime = System.nanoTime();
            System.out.printf("Recursive fib(%d): %d, Time: %d ns%n", 
                n, result, (endTime - startTime));

            startTime = System.nanoTime();
            result = fibIterative(n);
            endTime = System.nanoTime();
            System.out.printf("Iterative fib(%d): %d, Time: %d ns%n", 
                n, result, (endTime - startTime));
        }
    }
}

Expected output (approximate):

Recursive fib(10): 55, Time: 1000 ns
Iterative fib(10): 55, Time: 100 ns
Recursive fib(20): 6765, Time: 10000 ns
Iterative fib(20): 6765, Time: 200 ns
Recursive fib(30): 832040, Time: 100000 ns
Iterative fib(30): 832040, Time: 300 ns
Recursive fib(40): 102334155, Time: 1000000 ns
Iterative fib(40): 102334155, Time: 400 ns

Memory Usage
Recursive approach can cause stack overflow for large n
Iterative approach has constant memory usage

Example of stack overflow:

try {
    fibRecursive(100); // Will throw StackOverflowError
} catch (StackOverflowError e) {
    System.out.println("Stack overflow occurred");
}

Use Cases

Recursive Approach
Advantages:
- More intuitive and easier to understand
- Matches mathematical definition closely
- Good for small values of n (n < 40)
- Useful in educational contexts
Disadvantages:
- Poor performance for large n
- Risk of stack overflow
- Redundant calculations
- Not suitable for production use with large inputs
Iterative Approach
Advantages:
- Better performance for all input sizes
- Constant space usage
- No risk of stack overflow
- Suitable for production use
Disadvantages:
- Slightly more complex to understand
- Less intuitive than recursive solution
- Requires careful variable management

Best Practices

Input Validation

public static int fibIterative(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("Input must be non-negative");
    }
    if (n > 46) { // Maximum value that fits in int
        throw new IllegalArgumentException("Result would overflow int");
    }
    // ... rest of the implementation
}

Performance Optimization

public static int fibIterative(int n) {
    // Use lookup table for small values
    if (n <= 1) return n;

    // Use long to prevent overflow
    long prev = 0;
    long curr = 1;

    for (int i = 2; i <= n; i++) {
        long next = prev + curr;
        if (next > Integer.MAX_VALUE) {
            throw new ArithmeticException("Result would overflow int");
        }
        prev = curr;
        curr = next;
    }

    return (int)curr;
}

Testing

public class FibonacciTest {
    @Test
    public void testFibonacci() {
        // Test base cases
        assertEquals(0, fibRecursive(0));
        assertEquals(0, fibIterative(0));
        assertEquals(1, fibRecursive(1));
        assertEquals(1, fibIterative(1));

        // Test small values
        assertEquals(1, fibRecursive(2));
        assertEquals(1, fibIterative(2));
        assertEquals(2, fibRecursive(3));
        assertEquals(2, fibIterative(3));

        // Test larger values
        assertEquals(55, fibRecursive(10));
        assertEquals(55, fibIterative(10));

        // Test edge cases
        assertThrows(IllegalArgumentException.class, () -> fibRecursive(-1));
        assertThrows(IllegalArgumentException.class, () -> fibIterative(-1));
    }
}

Conclusion

For small values of n (n < 40), both approaches are viable
For larger values or production use, the iterative approach is recommended
The recursive approach is better for educational purposes and small inputs
The iterative approach is better for performance and memory efficiency
Both implementations should include proper input validation and overflow checking