返回python中递归函数的参数

Question

很抱歉，如果这是一个愚蠢的问题，我无法在网上找到解决方案(也许我只是不知道该搜索什么(。

如何返回"；找到"；这个递归函数的字典(我只能返回第n个号码(

注意：由于多种原因，简单地返回最后找到的不起作用

# Nth Fibonacci number generator
def nth_Rfib(n, found = {0:1, 1:1}):
if n in found:
return found[n]
else:
found[n] =  nth_Rfib(n-1, found) + nth_Rfib(n-2, found)
#print(found)
return found[n] # return found ** Doesn't Work **
print(nth_Rfib(5))  # 8
# instead, it should return: {0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8}

谢谢。

Answer 1

在这两种情况下，都需要返回found。但是，当您的函数返回dictionary时，您需要在递归调用它时访问所需的值：

def nth_Rfib(n, found = {0:1, 1:1}):
if n in found:
return found
else:
found[n] =  nth_Rfib(n-1, found)[n-1] + nth_Rfib(n-2, found)[n-2]
return found
print(nth_Rfib(5))

返回：

{0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8}

注意默认可变参数(如found = {0:1, 1:1}(可能存在的问题，例如：

>>> print(nth_Rfib(3))
{0: 1, 1: 1, 2: 2, 3: 3}
>>> print(nth_Rfib(5))
{0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8}
>>> print(nth_Rfib(3))
{0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8}

nth_Rfib(5)之后的nth_Rfib(3)返回相同的字典，因为您从未将其重置为默认的{0:1, 1:1}。

Answer 2

您需要一个返回数字的函数，以便递归表达式

found[n] = fib(n-1) + fib(n-2)

有意义；您还需要一个返回字典的函数，因为这是您最终想要返回的。

因此，定义两个不同的函数是有意义的，一个返回数字，另一个返回dict

def nth_Rfib(n):
found = {0: 0, 1: 1}
def fib(n):
if n not in found:
found[n] = fib(n-1) + fib(n-2)
return found[n]
fib(n)
return found

这使得found成为nth_Rfib的局部变量，但在fib的递归调用过程中充当全局变量。

它还完全消除了可变默认参数的任何奇怪之处。

>>> nth_Rfib(10)
{0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55}
>>> nth_Rfib(3)
{0: 0, 1: 1, 2: 1, 3: 2}