Java实现斐波那契数列并在溢出前停止的面试问题求解

Great question! Let’s unpack this clearly—your core idea has merit, but we need to distinguish between two separate issues here: integer overflow and stack overflow. Let’s break it down.

The Key Distinction: Integer Overflow vs. Stack Overflow #

• Integer Overflow: Happens when the next Fibonacci number exceeds the maximum value an int can hold (2,147,483,647). For Fibonacci, this occurs at the 47th number (which would be 2,971,215,073—way over the limit).
• Stack Overflow: Only occurs with recursive implementations, when the call stack gets too deep. Java’s default stack depth is usually 1000+ frames, but the 47th Fibonacci number only requires 46 recursive calls—so integer overflow will happen long before stack overflow in normal circumstances.

Solution 1: Iterative Implementation (No Stack Overflow Risk) #

Iteration is the safest approach because it doesn’t use the call stack for recursion, so stack overflow isn’t a concern. We just need to check if the next number would exceed Integer.MAX_VALUE before calculating it (to avoid generating invalid negative values from overflow).

Here’s the code:

public class FibonacciPrinter {
    public static void printFibonacciUntilLimit() {
        int prev = 0;
        int current = 1;
        
        // Print the first two base cases
        System.out.println(prev);
        System.out.println(current);
        
        while (true) {
            // Check if adding prev + current would overflow int
            if (current > Integer.MAX_VALUE - prev) {
                System.out.println("\nStopped: Next Fibonacci number would exceed Integer.MAX_VALUE");
                break;
            }
            
            int next = prev + current;
            System.out.println(next);
            
            // Shift values for next iteration
            prev = current;
            current = next;
        }
    }

    public static void main(String[] args) {
        printFibonacciUntilLimit();
    }
}

Solution 2: Recursive Implementation (Avoiding Both Overflows) #

If you want to use recursion, remember that integer overflow will trigger before stack overflow in normal JVM settings. We can add the same overflow check to stop recursion before either issue occurs.

Note: Java doesn’t optimize tail recursion, so deep recursion will still hit stack overflow eventually—but for int-based Fibonacci, we’ll never get that far.

Recursive code example:

public class RecursiveFibonacciPrinter {
    public static boolean printFibonacci(int prev, int current) {
        // Print the current value
        System.out.println(prev);
        
        // Check if next number would overflow
        if (current > Integer.MAX_VALUE - prev) {
            System.out.println(current);
            System.out.println("\nStopped: Next Fibonacci number would exceed Integer.MAX_VALUE");
            return false;
        }
        
        // Recurse with shifted values
        return printFibonacci(current, prev + current);
    }

    public static void main(String[] args) {
        printFibonacci(0, 1);
    }
}

Why Your Idea Works #

Your intuition to check against Integer.MAX_VALUE is spot-on because:

1. For iteration, it prevents invalid overflowed values and stops cleanly.
2. For recursion, it stops the process before we reach a stack depth that would cause stack overflow (since the 47th Fibonacci number is way below the stack’s limit).

In edge cases where someone intentionally reduces the JVM stack size (e.g., with -Xss128k), stack overflow could happen first—but that’s an extremely rare scenario in real-world code.

内容的提问来源于stack exchange，提问作者DXR