将计数器添加到递归斐波那契程序

Question

我正在使用基本的 Python MIT 免费课件，并且我已经运行通过递归练习进入了墙。原始程序接受一个整数并使用递归提供它的 Fibonacci。书中提供了该程序的脚本，但随后的练习要求输入一种方法，让程序识别在计算 fib(n) 的过程中执行了多少次 fib(2)。 ``

代码如下：

def fib(n):
    """Assumes n is int > 0
    Returns Fibonacci Number of n"""
    if n ==0 or n==1:
        return n        
    else:
        return fib(n-1) + fib(n-2)

def testfib(n):
    for i in range(n+1):
        print('fib of', i, 'is ', fib(i))

x=int(input('Enter a number: '))

print('Fibonacci of', x, 'is',fib(x))
print(testfib(x))

在另一个线程中给出了一个答案我正在努力思考并想知道是否有人可以解释其他部分中看起来像元组的东西如何在下面的代码中用作变量名称？参考：Trouble adding feature to recursive Fibonacci program

def fib(n):
    """Assumes n is int > 0
    Returns the nth Fibonacci number and number of times it was called"""
    if n == 0 or n == 1:
        return n, 0
    else:
        f1, count1 = fib(n-1)
        f2, count2 = fib(n-2)
        sum_counts = count1 + count2
        if n == 2:
            sum_counts = 1
        return f1 + f2, sum_counts


def testfib(n):
    for i in range(n+1):
        f, count = fib(i)
        print('fib of', i, 'is ', f, end="\t")
        print('count of fib(2) is ', count)

x = int(input('Enter a number: '))

print('Fibonacci of', x, 'is', fib(x)[0])
print(testfib(x))

Answer 1

逐行解释

f1, count1 = fib(n-1)

这里fib returns f1 + f2, sum_counts（见最后）所以f1 = f1 + f2和count1 = sum_counts

f2, count2 = fib(n-2)

这里fib returns f1 + f2, sum_counts（见最后）所以f2 = f1 + f2和count2 = sum_counts

return f1 + f2, sum_counts

fib 方法在这里返回 2 个值 f1 + f2, sum_counts 所以我们必须用元组或 2 个变量解包 2 个值

在您的代码中，我们通过 2 个变量解包值，下面是通过元组解包的示例

def test():
    return 1, 2, 3, 4, 5
my_list = test()
for val in my_list:
    print(val)

将计数器添加到递归斐波那契程序

Adding Counter to recursive Fibonacci program

python

recursion

fibonacci