递归斐波那契程序难以添加功能 [英] Trouble adding feature to recursive Fibonacci program

问题描述

我正在使用基本的Python MIT免费课件，并且遇到了递归练习的麻烦.原始程序采用整数，并使用递归提供其斐波那契.本书提供了该程序的脚本，但随后的练习要求为该程序输入一种方法，以识别 fib(2)在计算 fib(n).我希望得到一些帮助，因为我已经坚持了大约一个星期.

I'm working with a basic Python MIT free courseware and I have run into a wall with a recursion exercise. The original program takes an integer and provides its Fibonacci using recursion. The book provides the script for the program, but the subsequent exercise asks to input a way for the program to recognize how many times fib(2) is executed on its way to calculating fib(n). I'm hoping to get some help because I've been stuck on this for about a week now.

这是代码:

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))

参考:使用Python进行计算和编程简介，图4.7

推荐答案

将计数器包含在函数本身中，并使其返回两个值(斐波那契值和计数).这使您不必手动执行重置计数的业务逻辑.您可以根据需要多次调用该函数，计数将是正确的，而不是每次调用 fib 的每次 求和.

Include the counter inside the function itself and let it return two values (the fibonacci value and the count). This saves you from having to manually do the business logic of resetting the count. You can call the function as many times as you want and the counts will be correct, rather than summing counts from every time ever that fib was called.

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))

输出为:

Enter a number: 7
Fibonacci of 7 is 13
fib of 0 is  0  count of fib(2) is  0
fib of 1 is  1  count of fib(2) is  0
fib of 2 is  1  count of fib(2) is  1
fib of 3 is  2  count of fib(2) is  1
fib of 4 is  3  count of fib(2) is  2
fib of 5 is  5  count of fib(2) is  3
fib of 6 is  8  count of fib(2) is  5
fib of 7 is  13 count of fib(2) is  8
None

---

由于该问题对 n == 2 的情况有不同的处理，因此您可以在递归中使该情况成为另一个基本情况.

---

Since the problem treats the n == 2 case differently, you can make that another base case in your recursion.

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

这篇关于递归斐波那契程序难以添加功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！