How to count the number of times a value recurs in a recursive function?

Question

If you have a recursive function (e.g. the Fibonacci sequence):

def fib(n):
    """Return Fibonacci of n; assumes n is an int >= 0."""
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

How would one count, for example, the number of times fib(2) occurs when fib(20) is called?

Answer 1

You can use a decorator:

import functools

def count(f):
    """Count function calls."""
    @functools.wraps(f)
    def counted(*args, **kwargs):
        counted.count_calls += 1
        return f(*args, **kwargs)
    counted.count_calls = 0
    return counted

fib = count(fib)
fib(5)
fib.count_calls
# 15

Alternatively, you can now prepend any function definition using this decorator and the @ symbol:

@count
def fib(n):
    ...

fib(5)
fib.count_calls
# 15

Note, this decorator accumulates function calls:

fib(5)
fib(5)
fib.count_calls
# 30

This is a clever implementation that takes advantage of lesser known function attributes. Note, the original decorator is modified from John DiNero's count function discussed in his lecture on Memoization where he addresses this specific issue.

Answer 2

You can use a dictionary to count all invocations of fib. The dictionary has to be cleared before the first call to fib.

calls = defaultdict(int)

In the function, update the corresponding entry in the dictionary before doing anything else:

def fib(n):
  global calls
  """Assumes n an int >= 0
     Returns Fibonacci of n"""
  calls[n] += 1
  if n == 0 or n == 1:
    return 1
  else:
    return fib(n-1) + fib(n-2)

Answer 3

This is what i tried ... thinks like work fine

def fib(n):
    global counter
    if (n == 0 or n == 1):
        counter=counter+1
        return 1
    else:
        counter=counter+1
        return fib(n-1) + fib(n-2)
def countfib(n):
    global counter
    counter = 0
    fib(5);
    global count
    count=counter
    counter = 0
    return count
counter=0
count=0
print fib(5)
count=countfib(5)
print count

Output:

8
15

Answer 4

It's not clear to me exactly what the recurring values you want to count are, so I'm guessing it's the number of times the (recursive) function was called with the same argument (or group of them, if there's more than one).

In the code below, a decorator named tally_recurring_args() is used to wrap the function in some code to do this. To simplify things and avoid reinventing the wheel, a collections.Counter is used to tally the number of calls of every unique combination of arguments to the function. This is made a attribute of the function so it can be easily referenced in the wrapper every call to the decorated function.

import collections
import functools

def tally_recurring_args(func):
    func._args_counter = collections.Counter()  @ add attribute to func

    @functools.wraps(func)
    def wrapper(*args):
        key = ', '.join(str(arg) for arg in args)
        func._args_counter[key] += 1
        return func(*args)

    return wrapper

@tally_recurring_args
def fib(n):
    """Return Fibonacci of n; assumes n is an int >= 0."""
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

print('fib(5) -> {}'.format(fib(5)))
for args, count in sorted(fib._args_counter.items()):
    print('fib({}): called {} time{}'.format(args, count,
                                             's' if count > 1 else ''))

Output:

fib(5) -> 8
fib(0): called 3 times
fib(1): called 5 times
fib(2): called 3 times
fib(3): called 2 times
fib(4): called 1 time
fib(5): called 1 time

Answer 5

How about:

def fib(n, counts_dict):
    counts_dict[n] += 1
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n-1, counts_dict) + fib(n-2), counts_dict

Where counts_dict = collections.defaultdict(int)

Answer 6

def fib(n, x):
    c = 1 if n == x else 0

    if n == 0 or n == 1:
        return 1, c
    else:
        fA, cA = fib(n - 1, x)
        fB, cB = fib(n - 2, x)
        return fA + fB, cA + cB + c

If I've not messed up the logic, this function accepts n and x and returns a tuple (y, c) s.t. fib(n, _)=y and fib(x, _) was invoked c times during the calculation.

This is a purer alternative to the other proposed solutions that involve updating a dictionary. It rests on the assumption that OP only requires the number of times f(k, _) was invoked for one specific k, and so avoids filling a dictionary from which only one value is needed.

Answer 7

Without global variables:

from collections import defaultdict
def fib(n, count=None):
    if count is None:
        count = defaultdict(int)
    count[n] += 1
    if n in (0, 1):
        return 1, count
    return fib(n - 1)[0] + fib(n - 2)[0], count

The fib function now returns a tuple: the first element is the desired value and the second element is a dictionary containing the information of how many times each value the fib function was called on.

Answer 8

How about using an function attribute. Just like a static variable.

def fib(n): 
    """Return Fibonacci of n; assumes n is an int >= 0."""
    If hasattr(fib, 'cnt'):
        fib.cnt += 1
    else:
        fib.cnt = 1
    if n == 0 or n == 1: 
        return 1 
    else: 
        return fib(n-1) + fib(n-2)

fib.cnt =0

Answer 9

Using global:

c = 0
def fib(n):
    global c
    c += 1
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Answer 10

This is another solution without global variable, but done through value passing:

def fibo(n, c):
if n <= 2 and n > 0:
    return n-1, c
else:
    n1, c1 = fibo(n-1,c+1)
    n2, c2 = fibo(n-2,1)
    return n1+n2, c1+c2