如何计算斐波那契函数的累积调用次数？

Question

我试过了：

def fibonnaci(n):

        total_call = 0

        if n ==0 or n == 1:

            return 1

        else:

            if n== 2 or n == 1:

                total_call +=0

            else:

                total_call +=2

            return fibonnaci(n - 1) + fibonnaci(n - 2), total_call

n = 8

print(fibonnaci(n))

但我得到了一个错误：

TypeError: can only concatenate tuple (not "int") to tuple

如何显示斐波那契的通话次数？

Answer 1

使用装饰器使用函数属性参考法典def call_counter(func):    " Does the call count for any function "    def helper(x):        helper.calls += 1        return func(x)    helper.calls = 0    return helper@call_counterdef fib(n):  if n ==0 or n == 1:    return 1  return fib(n - 1) + fib(n - 2)用法fib(5)print(fib.calls)fib(10)print(fib.calls)  # Keeps running total so will be from previous                   # fib(5) plus current fib(10)# To reset counterfib.calls = 0使用类参考法典class countCalls(object):    """Decorator that keeps track of the number of times a function is called.    ::        >>> @countCalls        ... def foo():        ...     return "spam"        ...         >>> for _ in range(10)        ...     foo()        ...         >>> foo.count()        10        >>> countCalls.counts()        {'foo': 10}    Found in the Pythod Decorator Library from http://wiki.python.org/moin web site.    """    instances = {}    def __init__(self, func):        self.func = func        self.numcalls = 0        countCalls.instances[func] = self    def __call__(self, *args, **kwargs):        self.numcalls += 1        return self.func(*args, **kwargs)    def count(self):        "Return the number of times this function was called."        return countCalls.instances[self.func].numcalls    @staticmethod    def counts():        "Return a dict of {function: # of calls} for all registered functions."        return dict([(func.__name__, countCalls.instances[func].numcalls) for func in countCalls.instances])@countCallsdef fib(n):  if n ==0 or n == 1:    return 1  return fib(n - 1) + fib(n - 2)例print(fib(3))      # Output 3print(fib.count()) # Output 5优势允许获取所有已注册函数的计数（即使用装饰器注册）@countCallsdef f(n):  pass  # dummy function@countCallsdef g(n):  pass  # dummy functionfor i in range(5):  f(i)for i in range(10):  g(i)print(countCalls.counts())# Outputs: {'f': 5, 'g': 10}

Answer 2

def fib(n):&nbsp; &nbsp; if n <= 1:&nbsp; &nbsp; &nbsp; &nbsp; return n, 1&nbsp; &nbsp; fib_one = fib(n - 1)&nbsp; &nbsp; fib_two = fib(n - 2)&nbsp; &nbsp; #Return the result and the number of function calls (+ 1 for the current call)&nbsp; &nbsp; return fib_one[0] + fib_two[0], fib_one[1] + fib_two[1] + 1if __name__ == '__main__':&nbsp; &nbsp; number_of_function_calls = fib(4)[1]Fib（4） 应该返回 9，它确实如此&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fib(4)&nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fib(3)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fib(2)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; fib(2)&nbsp; &nbsp;fib(1)&nbsp; &nbsp;fib(1)&nbsp; &nbsp; &nbsp;fib(0)&nbsp; &nbsp; &nbsp; fib(1)&nbsp; fib(0)

Answer 3

问题是“显而易见的”，如果你费心去跟踪你正在使用的值：return&nbsp;fibonnaci(n&nbsp;-&nbsp;1)&nbsp;+&nbsp;fibonnaci(n&nbsp;-&nbsp;2),&nbsp;total_call当是 3 时，它尝试“添加”斐波那契（2），元组，和斐波那契（1），整数。这不是一项合法的行动。您需要正则化返回值。你不能神奇地只返回值（而不是计数），而这正是你想要的;你必须明确地编程差异：肢解元组并添加组件值。n1从您的基本案例开始return&nbsp;1,&nbsp;0递归情况需要添加组件。实施留给学生练习。