How to count cumulative calls of the Fibonacci function?

Question

I tried :

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

but I got a error:

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

How to display the number of calls for fibonnaci?

Answer 1

The problem is "obvious", if you bother to trace the values you're using:

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

When n is 3, this tries to "add" fibonnaci(2), a tuple, and fibonnaci(1), the integer 1. This is not a legal operation. You need to regularize your return values. You can't magically return the value alone (not the count) when that's what you want; you have to explicitly program the difference: dismember the tuple and add the component values.

Start with your base case being

return 1, 0

Your recursion case needs to add the components. Implementation is left s an exercise for the student.

Answer 2

def fib(n):

    if n <= 1:
        return n, 1
    fib_one = fib(n - 1)
    fib_two = fib(n - 2)
    #Return the result and the number of function calls (+ 1 for the current call)
    return fib_one[0] + fib_two[0], fib_one[1] + fib_two[1] + 1




if __name__ == '__main__':
    number_of_function_calls = fib(4)[1]

Fib(4) should return 9, which it does

                      fib(4)  
              fib(3)            fib(2)
          fib(2)   fib(1)   fib(1)     fib(0)
      fib(1)  fib(0)

Answer 3

In your return statement the result of both fibonnaci(n - 1) and fibonnaci(n - 2) could be a tuple (argument > 1), or a single integer (argument <= 1) thus + means concatenation when the first one is a tuple. But when n == 3 in return fibonacci(n - 1) + fibonacci(n - 2), total_call fibonacci(2) is a tuple ((2, total_call)), while fibonacci(1) is an integer (1). So you want to concatenate a tuple with with an integer, which is impossible.

Answer 4

Using Decorators

1. Using Function Attributes

Reference

Code

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_counter
def fib(n):
  if n ==0 or n == 1:
    return 1
  return fib(n - 1) + fib(n - 2)

Usage

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 counter
fib.calls = 0

2. Using Class

Reference

Code

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


@countCalls
def fib(n):
  if n ==0 or n == 1:
    return 1
  return fib(n - 1) + fib(n - 2)

Example

print(fib(3))      # Output 3
print(fib.count()) # Output 5

Advantage

Allows obtaining counts of all registered functions (i.e. registered by using decorator)

@countCalls
def f(n):
  pass  # dummy function

@countCalls
def g(n):
  pass  # dummy function

for i in range(5):
  f(i)

for i in range(10):
  g(i)

print(countCalls.counts())

# Outputs: {'f': 5, 'g': 10}

Answer 5

Here's another answer using a decorator. The advantage of using a decorator is that the base function fib does not need to change. That means the total_count code and multiple return values can be discarded from your original attempt -

@counter(model = fib_result)
def fib(n = 0):
  if n < 2:
    return n
  else:
    return fib(n - 1) + fib(n - 2)

Our decorator counter accepts a model so we can respond to the behavior of the decorated function. Our decorated fib will return a fib_result such as { result: ?, count: ? }. That means we also need to handle fib(?) + fib(?) which is why we also defined __add__ -

class fib_result:
  def __init__(self, result, count = 0):
    if isinstance(result, fib_result):
      self.result = result.result
      self.count = result.count + count
    else:
      self.result = result
      self.count = count
  def __add__(a, b):
    return fib_result(a.result + b.result, a.count + b.count)

As you can see, this fib_result is specific to counting fib calls. A different model may be required for counting other recursive functions that return other types of results.

All that's left now is to define our generic counter decorator. Our decorator takes arguments and returns a new decorator, lambda f: ..., which simply captures the passed arguments, lambda *args: ..., and constructs a new model with the result of f(*args) and a base count of 1 -

def counter(model = tuple):
  return lambda f: lambda *args: model(f(*args), 1)

Here's how the complete program works -

r = fib(4)
print(f"answer: {r.result}, recurs: {r.count}")
# answer: 3, recurs: 9

r = fib(10)
print(f"answer: {r.result}, recurs: {r.count}")
# answer: 55, recurs: 177