Java斐波那契数列第n项计算方法输入负数触发StackOverflowError
栈溢出根因定位
原来的代码在处理负数输入时存在两个致命错误,直接导致程序无法收敛:
- 递归参数无收敛:负数分支中执行
return (-1)^(n + 1) * fib(n);时,传入递归方法的参数还是原始负数值,没有缩小问题规模,形成无限自调用,最终耗尽栈空间触发StackOverflowError,这也是错误堆栈里所有栈帧都指向同一代码行的原因。 - 运算符误用:Java语言中
^是按位异或运算符,不是数学上的幂运算,原代码的写法根本无法实现负索引场景下需要的正负交替符号计算。
负索引斐波那契的计算规则
数学上负索引斐波那契(NegaFibonacci)的通用转换公式为:
F(-n) = (-1)^(n+1) * F(n)
这个规则的核心是,不需要为负数单独维护一套递归逻辑,只要将负数转换为对应的正索引值完成计算后,乘上对应符号系数即可,完全可以复用已经验证正确的正索引斐波那契计算能力。
修正后的代码实现
public int fib(int n) { // 递归终止条件:覆盖基础边界值 if (n == 0 || n == 1 || n == -1) { return Math.abs(n); } // 负数分支:转换为正索引计算,匹配符号系数 if (n < 0) { // 按公式计算符号:(-1)的(n+1)次幂 int sign = ((n + 1) % 2 == 0) ? 1 : -1; // 递归计算对应正索引的斐波那契值,确保参数收敛 return sign * fib(-n); } // 原有正索引的递归逻辑保持不变 return fib(n - 1) + fib(n - 2); }
逻辑正确性验证
修正后可匹配标准负斐波那契数列的预期结果:
- 输入
n=-1:返回1 - 输入
n=-2:返回-1 - 输入
n=-3:返回2 - 输入
n=-4:返回-3 - 输入
n=-5:返回5
上述结果完全符合负索引斐波那契的数列定义,不存在无限递归的栈溢出问题。
内容的提问来源于stack exchange,提问作者user14371065
相关产品推荐
相关产品推荐

