Intellij Idea Python中的递归函数用于Fibonacci序列

cvxl0en2 于 12个月前发布在 Python

关注(0)|答案(4)|浏览(133)

我正在尝试使用递归函数来计算斐波那契数列。这是我的想法：

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]
    if 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 fiboonacci value: "))
result = fibonacci(number)
print(f"The value of fibbonaci {number} is {result}")

我使用了chatGPT，以便我可以有一个基本的想法来实现该方法。我收到的错误是RecursionError：已超过最大递归深度。即使对于int 5，我也会收到这个错误。我是一个初学者在编程，我试图实现递归函数，使我有一个适当的想法有关的运作。有人能帮我解决这个错误吗？
当我收到错误时，我试图使用sys函数来设置递归限制。在这种情况下，重复是1000+。我希望递归函数能正常工作。但我仍然收到错误。

intellij-idea

来源：https://stackoverflow.com/questions/76836669/recursive-function-in-python-for-fibonacci-sequence

4条答案

按热度按时间

brqmpdu11#

正如已经指出的，这里的核心问题是需要考虑两种特殊情况，n == 1和n == 0。您可以在代码中这样做，但由于您是手动初始化缓存，因此您也可以在那里这样做。

## ----------------
## initialize our cache in a way that will
## handle our special cases. Note that this
## also simplifies our method.
## ----------------
fibonacci_cache = {0: 0, 1: 1}
## ----------------

def fibonacci(n):
    if n not in fibonacci_cache:
        fibonacci_cache[n] = fibonacci(n-1) + fibonacci(n-2)
    return fibonacci_cache[n]

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

此时，您可以添加一个测试来确保n >= 0，如果不是，则抛出一个ValueError，但我将把这个问题留给您考虑。

赞(0）回复(0）举报 12个月前

pkln4tw62#

当您的代码到达fibonacci(2)的递归调用时，问题就出现了。
在这个调用中，它将调用fibonacci(1)和fibonacci(0)。
在fibonacci(1)调用中，它将遇到if n == 1条件，并以返回值1正确终止。
但是fibonacci(0)调用并没有停止;它调用fibonacci(-1)和fibonacci(-2)。从那以后，负数就一直在增长。
你需要考虑n为零的情况。

赞(0）回复(0）举报 12个月前

axkjgtzd3#

假设n=2，你的函数中的else会被满足，那么它面对fibonacci(n - 1) + fibonacci(n - 2)，也就是fibonacci(1) + fibonacci(0)。
fibonacci(1)是1，但是你没有为fibonacci(0)提供任何东西，所以你的else也会被满足，你会得到fibonacci(-1) + fibonacci(-2)，这将无限发生。
因此，只需为n=0提供一个返回值：

def fibonacci(n):
    if n in fibonacci_cache:
        return fibonacci_cache[n]
    if n == 0:
        return 0
    if n == 1:
        return 1
    ...

赞(0）回复(0）举报 12个月前

ua4mk5z44#

看看你的函数在接收到n=2时会做什么

赞(0）回复(0）举报 12个月前