递归斐波那契数列触发RecursionError的原因及解决办法

问题原因

你的递归函数缺少关键的边界条件处理：

• 当前代码只定义了n == 1时返回1，但计算fibonacci(2)时，会执行fibonacci(1) + fibonacci(0)；
• fibonacci(0)会进入else分支，调用fibonacci(-1) + fibonacci(-2)，以此类推，递归会不断向负数方向延伸，形成无限递归，最终触发RecursionError，哪怕输入5这种小数字也会出问题。

解决办法

根据斐波那契数列的常规定义，补充对应的边界条件即可。常见的两种定义方式及修正代码如下：

方式1：定义F(1)=1，F(2)=1

修改函数，增加n == 2的判断：

import sys
new_recursion_limit=3000
sys.setrecursionlimit(new_recursion_limit)
fibonacci_cache = {}

def fibonacci(n):
    if n in fibonacci_cache:
        return fibonacci_cache[n]
    # 补充n=2的边界条件
    if n == 1 or n == 2:
        return 1
    else:
        result = fibonacci(n - 1) + fibonacci(n - 2)
        fibonacci_cache[n] = result
        return result


number = int(input("Enter the number for fibonacci value: "))
result = fibonacci(number)
print(f"The value of fibonacci {number} is {result}")

方式2：定义F(0)=0，F(1)=1

如果需要支持从0开始的斐波那契数列，修改边界条件为：

import sys
new_recursion_limit=3000
sys.setrecursionlimit(new_recursion_limit)
fibonacci_cache = {}

def fibonacci(n):
    if n in fibonacci_cache:
        return fibonacci_cache[n]
    # 补充n=0的边界条件
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        result = fibonacci(n - 1) + fibonacci(n - 2)
        fibonacci_cache[n] = result
        return result


number = int(input("Enter the number for fibonacci value: "))
result = fibonacci(number)
print(f"The value of fibonacci {number} is {result}")

额外建议：可以在函数开头增加输入合法性判断，避免用户输入负数导致的递归问题：

def fibonacci(n):
    if not isinstance(n, int) or n < 0:
        raise ValueError("n must be a non-negative integer")
    # 后续逻辑...

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