Как подсчитать количество повторений значения в рекурсивной функции?

Question

Если у вас есть рекурсивной функции (например, последовательность Фибоначчи):

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) 

Как бы один граф, например, количество раз Фибо (2) происходит, когда выдумка (20) называется?

Answer 1

Вы можете использовать словарь, чтобы подсчитывать все вызовы fib. Словарь должен быть очищен до первого вызова fib.

calls = defaultdict(int) 

В функции, обновить соответствующую запись в словаре, прежде чем делать что-нибудь еще:

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 2

Как о:

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 

Где counts_dict = collections.defaultdict(int)

Answer 3

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 

Если Я не перепутал логику, эта функция принимает n и x и возвращает кортеж (y, c) s.t. fib(n, _)=y и fib(x, _) было вызвано c раз во время расчета.

Это более чистая альтернатива другим предлагаемым решениям, которые включают в себя обновление словаря. Он основывается на предположении, что для ОП требуется только количество раз f(k, _) было вызвано для одного конкретного k и поэтому позволяет избежать заполнения словаря, из которого требуется только одно значение.

Answer 4

Вы можете использовать декоратор:

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 

В качестве альтернативы, вы можете предварять любое определение функции с помощью этого декоратора и @ символа:

@count 
def fib(n): 
    ... 

fib(5) 
fib.count_calls 
# 15 

Примечания Этого декоратора накапливает вызовы функций:

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

Это умная реализация, которая принимает antage менее известного function attributes. Обратите внимание: оригинальный декоратор изменен из функции count от John DiNero, обсуждаемой в его lecture on Memoization, где он решает эту проблему.

Answer 5

Без глобальных переменных:

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 

fib функция теперь возвращает кортеж: первый элемент требуемого значения, а второй элемент представляет собой словарь, содержащий информацию о том, сколько раз каждое значение функции fib было .

Answer 6

Это то, что я пробовал ...думает, как работают отлично

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 

Выход:

Answer 7

Как об использовании атрибута функции. Также как статическая переменная.

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 8

Это мне не ясно, какие именно повторяющиеся значения, которые вы хотите считать это, так что я предполагаю, что это число раз функция (рекурсивный) была вызвана тем же аргументом (или группу из них, если их больше одного).

В приведенном ниже кодере декоратор с именем tally_recurring_args() используется для обертывания функции в некотором коде для этого. Чтобы упростить ситуацию и избежать повторного использования колесика, collections.Counter используется для подсчета количества вызовов каждой уникальной комбинации аргументов функции. Это делается атрибутом функции, поэтому на вызов в декодированную функцию можно легко ссылаться в wrapper.

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

Выход:

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